題目描述（中等難度）

這道題的的難度我覺得理解題意就占了一半。題目的意思是給定一個數(shù)，然后將這些數(shù)字的位置重新排列，得到一個剛好比原數(shù)字大的一種排列。如果沒有比原數(shù)字大的，就升序輸出。

關(guān)鍵就是剛好是什么意思？比如說原數(shù)字是 A，然后將原數(shù)字的每位重新排列產(chǎn)生了 B C D E，然后把這 5 個數(shù)字從小到大排列，比如是 D A B E C ,那么，我們要找的就是 B，就是那個剛好比 A 大的數(shù)字。

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

題目還要求空間復(fù)雜度必須是 O（1）。

解法一

我們想幾個問題。

要想使得數(shù)字變大，只要任意一位變大就可以。

要想得到剛好大于原來的數(shù)字，要變個位。

這里變大數(shù)字，只能利用交換。

如果從個位開始，從右往左進(jìn)行，找一個比個位大的，交換過來，個位的數(shù)字交換到了更高位，由于個位的數(shù)字較小，所以交換過去雖然個位變大了，但數(shù)字整體變小了。例如 1 3 2，把 2 和 3 交換，變成 1 2 3，個位變大了，但整體數(shù)字變小了。

個位不行，我們再看十位，如果從十位左邊找一個更大的數(shù)字交換過來，和個位的情況是一樣的，數(shù)字會變小。例如 4 1 2 3，把 2 和 4 交換，2 1 4 3，數(shù)字會變小。如果從右邊找一個更大的數(shù)字交換過來，由于是從低位交換過來的，所以數(shù)字滿足了會變大。如 4 1 2 3，把 2 和 3 交換，變成 4 1 3 2 數(shù)字變大了。

如果十位右邊沒有比十位數(shù)字大的，我們就左移看下一位，再看當(dāng)前位右邊，有沒有更大的數(shù)字，沒有就一直左移就可以。

還有一個問題，如果右邊有不止一個大于當(dāng)前位的數(shù)字選哪個？選那個剛好大于當(dāng)前位的，這樣會保證數(shù)字整體盡可能的小。

交換完結(jié)束了嗎？并沒有。因為交換完數(shù)字變大了，但并不一定是剛好大于原數(shù)字的。例如 158476531，我們從十位開始，十位右邊沒有大于 3 的。再看百位，百位右邊沒有大于 5 的。直到 4 ，右邊出現(xiàn)了很多大于 4 的，選那個剛好大于 4 的，也就是 5 。然后交換，變成 158576431，數(shù)字變大了，但并不是剛好大于 158476531，我們還需要將 5 右邊的數(shù)字從小到大排列。變成158513467，就可以結(jié)束了。

而最后的排序，我們其實并不需要用排序函數(shù)，因為交換的位置也就是 5 的右邊的數(shù)字一定是降序的，我們只需要倒序即可了。看一下 LeetCode 提供的動圖更好理解一些。

再看這個過程，我們其實是從右向左找到第一個數(shù)字不再遞增的位置，然后從右邊找到一個剛好大于當(dāng)前位的數(shù)字即可。

再看下代碼吧。

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);
    //利用倒置進(jìn)行排序
    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--;
    }
}

時間復(fù)雜度：最壞的情況就是遍歷完所有位，O（n），倒置也是 O（n），所以總體依舊是 O（n）。

空間復(fù)雜度：O（1）。

總

開始看題的時候一直沒理解，后來理解了題試了幾種也沒想出來，然后看了 Solution，理了下思路。

更多詳細(xì)通俗題解詳見 leetcode.wang 。