# Previous Permuation

``````给出排列[1,3,2,3]，其上一个排列是[1,2,3,3]

``````

``````排列中可能包含重复的整数
``````

## Solution

1. 从后往前寻找索引满足 a[k] > a[k + 1], 如果此条件不满足，则说明已遍历到最后一个。
2. 从后往前遍历，找到第一个比a[k]小的数a[l], 即a[k] > a[l].
3. 交换a[k]与a[l].
4. 反转k + 1 ~ n之间的元素。

## Code

``````public class Solution {
/**
* @param nums: A list of integers
* @return: A list of integers that's previous permuation
*/
public ArrayList<Integer> previousPermuation(ArrayList<Integer> nums) {
if (nums == null || nums.size() <= 1) {
return nums;
}
// step1: find nums[i] > nums[i + 1]
int i = 0;
for (i = nums.size() - 2; i >= 0; i--) {
if (nums.get(i) > nums.get(i + 1)) {
break;
} else if (i == 0) {
// reverse nums if reach minimum
reverse(nums, 0, nums.size() - 1);
return nums;
}
}
// step2: find nums[i] > nums[j]
int j = 0;
for (j = nums.size() - 1; j > i; j--) {
if (nums.get(i) > nums.get(j)) {
break;
}
}
// step3: swap betwenn nums[i] and nums[j]
Collections.swap(nums, i, j);
// step4: reverse between [i + 1, n - 1]
reverse(nums, i + 1, nums.size() - 1);

return nums;
}

private void reverse(List<Integer> nums, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
Collections.swap(nums, i, j);
}
}
}
``````