31. 下一个排列

思路：

我们希望找到一种方法，能够找到一个大于当前序列的新序列，且变大的幅度尽可能小。

• 我们需要将一个左边的「较小数」与一个右边的「较大数」交换，以能够让当前排列变大，从而得到下一个排列。同时我们要让这个「较小数」尽量靠右，而「较大数」尽可能小。
• 当交换完成后，「较大数」右边的数需要按照升序重新排列。这样可以在保证新排列大于原来排列的情况下，使变大的幅度尽可能小。
• 对于上面的第二句其实就是交换了以后使得我们被提前的那个数字后面的各位数字都是升序，这样后面的排列就是最小的，而且按照我们第一个步骤的筛选，我们要排序的是一个降序，我们把他改成升序

代码：

class Solution {
    public void nextPermutation(int[] nums) {
        //如果从尾到头遍历一直是升序的，那么就反转数组
        //如果从尾到头遍历有降序，那么置换他俩
        //1 5 3 2
        int i=nums.length-2;

        //从右侧开始找，找到一个左边小右边大的停止
        while (i>=0&&nums[i]>=nums[i+1]){
            i--;
        }

        //如果能找到
        if (i>=0){
            int j=nums.length-1;
            //从右开始找，找到第一个大于i的数字交换
            while (j>=0&& nums[i]>=nums[j]){
                j--;
            }
            swap(nums,i,j);
        }
        reverse(nums, i+1);
    }
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


    //倒置start到最后一个元素直接的数组
    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

}