LC31 - 下一个排列

这题直接举个例子更直观
{1, 5, 8, 4, 7, 6, 5, 3, 1} 这样一个序列，我们想找比他大的下一个排序，那么首先要从后往前找第一个非升序的数字，也就是a[i] < a[i+1]的第一个（如果整个数组都是降序排列，说明它已经是最大的排列了，直接反转数组得到第一个排列），于是我们找到了4。这时候为了得到更大的序列，我们需要把4和它后面的一个比它大的数字交换，同时为了使交换之后的序列增大最小，我们需要找到从后往前第一个比4大的数字，于是我们又找到了5，将他们交换后得到 {1, 5, 8, 5, 7, 6, 4, 3, 1}， 最后将交换完成后的5之后的序列从小到大重排序，得到{1, 5, 8, 5, 1, 3, 4, 6, 7}就是原排列的下一个排列了。

代码如下

class Solution {
    public void nextPermutation(int[] nums) {
        if(nums == null && nums.length <= 1) return;
        int i = nums.length - 2;
        while(i>=0 && nums[i] >= nums[i+1]){
            i--;
        }
        if(i < 0){
            reverseArray(nums, 0);
            return;
        }
        for(int j = nums.length - 1; j>i; j--){
            if(nums[i] < nums[j]){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
                break;
            }
        }
        reverseArray(nums, i+1);

    }

    public static void reverseArray(int[] a, int start){
        int l = start;
        int r = a.length - 1;
        while(l < r){
            int tmp = a[l];
            a[l] = a[r];
            a[r] = tmp;
            l++;
            r--;
        }
    }
}