给定一个整数数组来表示排列，找出其之后的一个排列。

在线评测地址：领扣题库官网

例1:

输入:[1]
输出:[1]
例2:
输入:[1,3,2,3]
输出:[1,3,3,2]
例3:
输入:[4,3,2,1]
输出:[1,2,3,4]

算法

• 从后往前寻找不是递增的下标i
  从后往前遍历数组，如果一直是逐渐增大的，则已经是最大的了，如果出现了一个下降的数，那么遍历就到此为止，因为这已遍历的部分就可以排列成下一个较大的数了

发现找到 i为3 ， a[3]=4就不是递增了
当找到这个突然下降的点A后，由于它后面已经排列为“最大”，因为A后面是完全降序的降序
在例子里 就是 7 6 5 3 2 降序

• 然后从i 往后找到比下标i 对应的数字大的 且值最小的那个，令它为k，
  发现 k为6，a[6]=5 是比4大的，而且还是5还是最小的一个
• 交换i k
  交换完毕 序列成了

1 11 12 5 7 6 4 3 2
这样的序列已经比原序列大了

• 然后把从i+1到整个数组最后一个反转

1. 11 12 5 2 3 4 6 7

这样既能保证比原序列大，而且i+1到结尾原本是降序的，说明是最大的排列，现在成了升序 i+1到结尾这一部分就成了最小的排列了
既能保证比原序列大，还尽可能的小，所以是原序列的下一个排列

• 如果一直没有找到下降的点，则全部逆转即可。（从完全的降序改为了升序）

复杂度分析

时间复杂度
因为要遍历一遍数组 所以是O(N)的
空间复杂度
没有新开辟空间，所以还是O(N)

public class Solution {
    /**
     * @param nums: An array of integers
     * @return: nothing
     */
    public void nextPermutation(int[] nums) {
            int i=nums.length-2;
        while(i>=0&&nums[i]>=nums[i+1]){
                i--;
        }
        // i>=0 说明nums不是完全降序的 
        if(i>=0){
                //从i往后找，找到比i大的，且最小的那个 
                int j=i+1;
                while(j<nums.length&&nums[j]>nums[i]){
                        j++;
                }
                j--;
                // 交换i和j 
                int tmp=nums[i];
                nums[i]=nums[j];
                nums[j]=tmp;
        }
        //反转i之后的数组，让之前的从后往前的递增部分改成了从前往后递增，这样才能是下一个排列 
        i=i+1;
        int j=nums.length-1;
        while(i<j){
                int tmp=nums[i];
                nums[i]=nums[j];
                nums[j]=tmp;
                i++;
                j--;
        }
    }
}

更多题解参考：九章官网solution