Given a list of integers, which denote a permutation.

Find the previous permutation in ascending order.

Notice

The list may contains duplicate integers.

Have you met this question in a real interview?

Yes

Example

For[1,3,2,3], the previous permutation is[1,2,3,3]

For[1,2,3,4], the previous permutation is[4,3,2,1]

public class Solution {
    /*
     * @param nums: A list of integers
     * @return: A list of integers that's previous permuation
     */
    public List<Integer> previousPermuation(List<Integer> nums) {
        // write your code here
        //1,2,3,4
        //1,2,4,3
        //1,3,2,4
        //1,3,4,2
        //1,4,2,3
        //1,4,3,2
        //2,1,2,3
        //2,1,3,2
        //3,4,2,1
        //2,4,1,2
        //4,1,2,2

        //so the rule is find the first ascending digit i, and among ((i + 1), nums.length),
        //find the largest digits that's smaller than digit i

        if (nums == null || nums.size() < 2) {
            return nums;
        }

        int i;
        for (i = nums.size() - 1; i > 0; i--) {
            if (nums.get(i - 1) > nums.get(i)) {
                break;
            }
        }
        if (i == 0) {
            reverse(0, nums);
            return nums;
        }

        int maxIndex = i;
        int maxNum = nums.get(i);

        for (int j = i; j < nums.size(); j++) {
            if (nums.get(j) < nums.get(i - 1) && nums.get(j) >= maxNum) {
                maxNum = nums.get(j);
                maxIndex = j;
            }
        }

        swap(i - 1, maxIndex, nums);
        reverse(i, nums);
        return nums;
    }

    public void swap(int a, int b, List<Integer> nums) {
        int bNew = nums.get(a);
        nums.set(a, nums.get(b));
        nums.set(b, bNew);
    }

    public void reverse(int start, List<Integer> nums) {
        int end = nums.size() - 1;
        while (start < end) {
            swap(start, end, nums);
            start++;
            end--;
        }
    }
}