力扣思维题/经典面试题——下一个排序

https://leetcode.cn/problems/next-permutation/description/
字节面试题，非常经典的逻辑思维题

1、找到第一个下降点，说明这个点可以变得稍微大一点以至于让整个排列变得更加大
为什么，仔细想想，后面都是倒序了怎么都不可能变得更加大了

2、下降点变成多大呢？变成后面比它大的最小的数就可以了

3、这一位已经比原来的大了，后面不管怎么样，这个排列都会比原来的大，要是这个排列尽可能地小，只需要对后面的排个序

可以看一下这张图更加容易理解：
代码：

class Solution {
   
    public void nextPermutation(int[] nums) {
   
        //从右至左找第一个下降点，如果找不到，说明是倒序排序翻转一下就可以了
        int down = -1;
        int cur = nums.length-1;
        while(cur>=1){
   
            if(nums[cur]>nums[cur-1]){
   
                down = cur-1;
                break;
            }
            cur--;
        }
        //找不到
        if(down==-1){
   
            for(int i=0;i<nums.length/2;i++){
   
                int temp = nums[i];
                nums[i] = nums[nums.length-i-1];
                nums[nums.length-i-1] = temp;
            }
            return ;
        }
        //找翻转哪一个点
        while(cur<nums.length){
   
            if(nums[cur]<=nums[down])
               break; 
            cur++;
        }
        //找到的是第一个小于等于down的，还要再-1;
        cur--;
        //这个数移到down
        int temp = nums[cur];
        nums[cur] = nums[down];
        nums[down] = temp;
        //再排个序
        //可以使用翻转，因为后面必定倒序
        //1、Arrays.sort(nums,down+1,nums.length);
        //局部反转写起来容易错，还是推荐直接排序
        for(int i=1;i<=(nums.length-(down+1)+1)/2;i++){
   
            int t = nums[down+i];
            nums[down+i] = nums[nums.length-i];
            nums[nums.length-i] = t;
        }
    }
}