31. Next Permutation.java

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
12345 -> 12354 -> 12435 -> 12453 -> 12534
class Solution {
    public void nextPermutation(int[] nums){
        if(nums == null || nums.length < 2){
            return;
        }
        for(int i = nums.length - 2; i >= 0; i--){
//应维持降序，就没空间改进了，直到找到打破规律变为升序的这个元素：这个元素之后没法改进了，所以当前这位就要替换成大一点的数：在后面元素里找刚刚比他大的（相当于进位到这个数（比当前大的最小数）了）
            if(nums[i] < nums[i + 1]){ //只要是升序，就说明有改进空间，通过和后面某元素交换
                for(int j = nums.length - 1; j > i; j--){ //后半部分已经是降序了，所以从后往前找第一个比nums[i]大的元素
                    if(nums[j] > nums[i]){
                        swap(nums, i, j);
                        break;
                    }     //换完之后，后半部分还是维持降序（因为换了更小元素过来）
                }
                swapList(nums, i + 1, nums.length - 1);  //把这个降序变为升序，才能让整体变小，成为真正的next permutation
                break;
            }
            if(i == 0){ //说明整个数组就是降序排列的
                swapList(nums, 0, nums.length - 1);
            }
        }
    }
    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public void swapList(int[] nums, int start, int end){
        while(start < end){
            swap(nums, start++, end--);
        }
    }
}