2.6 實例5：下一個更大排列

將數字重新排列為下一個更大排列。如果無法進行這種排列，則必須將其重新排列為最小排列（即升序排列）。例如（輸入在左列，其相應的輸出在右列）：

1，2，3→1，3，2

3，2，1→1，2，3

1，1，5→1，5，1

對于數字排列1，2，3，比當前數字排列更大的下一個排列就是1，3，2。而對于3，2，1，無法找到下一個比當前數字排列更大的排列，因此必須輸出數字排列的升序排列。

思路：首先在數組中從后往前找到一個下降的數字，添加索引為i；然后從后往前找到第一個比當前索引i所在的數值要大的索引j，交換索引位置i以及j的數值；最后，把索引i以后的所有值從小到大排序，如圖2-7～圖2-9所示。

復雜度分析：時間復雜度為O（n），空間復雜度為O（1）。

如果現在要求解先前的數字排列，思路正好相反。對于數組nums，首先找到第一個遞增的數，添加索引為p，然后找到第一個比當前nums[p]小的數的索引q，交換這兩個數，最后需要把索引p+1后面的數從大到小排列。

如果面試官讓你求解下一個較大的數值，思路和本題一樣。

當然本題還可以進一步優化，比如利用二分法來尋找比nums[p]大的數的索引q，因為p+1以后的數組都是排好序的。