题目描述（中等难度）

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

关键就是刚好是什么意思？比如说原数字是 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 提供的动图更好理解一些。

再看下代码吧。

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

空间复杂度：O（1）。

总

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

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^