lintcode51- Previous Permutation- medium

Given a list of integers, which denote a permutation.

Find the previous permutation in ascending order.

Notice

The list may contains duplicate integers.

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 List<Integer> previousPermuation(List<Integer> nums)

算法：和前面的类似，就是反一反，关键是明白字典序排列是怎么产生的。原则是维持尽可能多的前缀，所以要尽量换后面的排列。所以从前往后就是在最后找尽量的不能动手脚的下降序列，然后对他们动手（就是迂回通过找最后面出现的上升对来实现，因为这个上升对后面肯定就是降序了，否则这一对不会是从后往前第一个找到的）。反过来如果从后字典序往前找，就是要找落在后头的尽量长的不能动手的上升序列（如果最后下降的话你直接换一下就可以得到前一个了啊），然后对他们动手。

本题具体步骤：

1.从后往前找第一个出现的下降对prev-next。

2.在next~最后中找出第一个比prev小的数字smaller。

3.交换prev和smaller。

4.在现在新的next~最后里排成降序（做逆序操作）

细节：1.对List数据结构操作的话，赋值记得用list.set(idx, obj)，不要remove又add，这样很麻烦。当然list.get() = xxx这种对常数赋值的操作是肯定错误的。2.for(int i = 0, j = nums.length -1; ...; )，这里面同时创造ij并赋值，记得写一个int就好了，同行写两个不可能用逗号隔开啊，所以肯定不行的，基础语法。

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) {

        //这里实现类型有讲究吗
        List<Integer> result = new ArrayList<Integer>(nums);
        
        int prev = 0;
        int next = 0;
        for (int i = nums.size() - 2; i >= 0; i--) {
            if (nums.get(i) > nums.get(i + 1)) {
                prev = i;
                next = i + 1;
                break;
            }
        }
        
        if (prev == next) {
            reverse(result, 0, result.size() - 1);
            return result;
        }
        
        int smaller = next;
        for (int i = nums.size() - 1; i > next; i--) {
            if (nums.get(i) < nums.get(prev)) {
                smaller = i;
                break;
            }
        }
        
        swap(result, prev, smaller);
        reverse(result, next, result.size() - 1);
        
        return result;
    }
    
    
    // 想看swap怎么写的，用set写的吗
    private void swap(List<Integer> nums, int idx1, int idx2) {
        int temp = nums.get(idx1);
        nums.set(idx1, nums.get(idx2));
        nums.set(idx2, temp);
    }
    
    private void reverse(List<Integer> nums, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            swap(nums, i, j);
        }
    }
}