给定一个整数数组来表示排列，找出其之后的一个排列。
在线评测地址：领扣题库官网
例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到整个数组最后一个反转
- 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
