题目描述（中等难度）

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

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

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

再看下代码吧。

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

}

private void swap(int[] nums, int i, int j) {
    int temp = nums[j];
    nums[j] = nums[i];
    nums[i] = temp;
}

private void reverse(int[] nums, int start) {
    int i = start, j = nums.length - 1;
    while (i < j) {
        swap(nums, i, j);
        i++;
        j--;
    }
}

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

空间复杂度：O（1）。

总

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

作者：windliang

来源：https://windliang.cc