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--;
        }
    }

}