这道题的的难度我觉得理解题意就占了一半。题目的意思是给定一个数，然后将这些数字的位置重新排列，得到一个刚好比原数字大的一种排列。如果没有比原数字大的，就升序输出。

关键就是刚好是什么意思？比如说原数字是 A，然后将原数字的每位重新排列产生了 B C D E，然后把这 5 个数字从小到大排列，比如是 D A B E C ,那么，我们要找的就是 B，就是那个刚好比 A 大的数字。

再比如 123，其他排列有 132，213，231，312，321，从小到大排列就是 123 132 213 231 312 321，那么我们要找的就是 132。

题目还要求空间复杂度必须是 O（1）。

解法一

我们想几个问题。

要想使得数字变大，只要任意一位变大就可以。

要想得到刚好大于原来的数字，要变个位。

这里变大数字，只能利用交换。

如果从个位开始，从右往左进行，找一个比个位大的，交换过来，个位的数字交换到了更高位，由于个位的数字较小，所以交换过去虽然个位变大了，但数字整体变小了。例如 1 3 2，把 2 和 3 交换，变成 1 2 3，个位变大了，但整体数字变小了。

个位不行，我们再看十位，如果从十位左边找一个更大的数字交换过来，和个位的情况是一样的，数字会变小。例如 4 1 2 3，把 2 和 4 交换，2 1 4 3，数字会变小。如果从右边找一个更大的数字交换过来，由于是从低位交换过来的，所以数字满足了会变大。如 4 1 2 3，把 2 和 3 交换，变成 4 1 3 2 数字变大了。

如果十位右边没有比十位数字大的，我们就左移看下一位，再看当前位右边，有没有更大的数字，没有就一直左移就可以。

还有一个问题，如果右边有不止一个大于当前位的数字选哪个？选那个刚好大于当前位的，这样会保证数字整体尽可能的小。

交换完结束了吗？并没有。因为交换完数字变大了，但并不一定是刚好大于原数字的。例如 158476531，我们从十位开始，十位右边没有大于 3 的。再看百位，百位右边没有大于 5 的。直到 4 ，右边出现了很多大于 4 的，选那个刚好大于 4 的，也就是 5 。然后交换，变成 158576431，数字变大了，但并不是刚好大于 158476531，我们还需要将 5 右边的数字从小到大排列。变成158513467，就可以结束了。

而最后的排序，我们其实并不需要用排序函数，因为交换的位置也就是 5 的右边的数字一定是降序的，我们只需要倒序即可了。看一下 LeetCode 提供的动图更好理解一些。

再看这个过程，我们其实是从右向左找到第一个数字不再递增的位置，然后从右边找到一个刚好大于当前位的数字即可。

再看下代码吧。

publicvoidnextPermutation(int[] nums) {
inti=nums.length-2;
//找到第一个不再递增的位置while (i>=0&&nums[i+1] <=nums[i]) {
i--;
    }
//如果到了最左边，就直接倒置输出if (i<0) {
reverse(nums, 0);
return;
    }
//找到刚好大于 nums[i]的位置intj=nums.length-1;
while (j>=0&&nums[j] <=nums[i]) {
j--;
    }
//交换swap(nums, i, j);
//利用倒置进行排序reverse(nums, i+1);
}
privatevoidswap(int[] nums, inti, intj) {
inttemp=nums[j];
nums[j] =nums[i];
nums[i] =temp;
}
privatevoidreverse(int[] nums, intstart) {
inti=start, j=nums.length-1;
while (i<j) {
swap(nums, i, j);
i++;
j--;
    }
}

时间复杂度：最坏的情况就是遍历完所有位，O（n），倒置也是 O（n），所以总体依旧是 O（n）。

空间复杂度：O（1）。

总

开始看题的时候一直没理解，后来理解了题试了几种也没想出来，然后看了 Solution，理了下思路