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所示。

图2-7 下一个更大排列（1）

图2-8 下一个更大排列（2）

图2-9 下一个更大排列（3）

代码清单2-14 下一个更大排列

复杂度分析：时间复杂度为O（n），空间复杂度为O（1）。

如果现在要求解先前的数字排列，思路正好相反。对于数组nums，首先找到第一个递增的数，添加索引为p，然后找到第一个比当前nums[p]小的数的索引q，交换这两个数，最后需要把索引p+1后面的数从大到小排列。

如果面试官让你求解下一个较大的数值，思路和本题一样。

当然本题还可以进一步优化，比如利用二分法来寻找比nums[p]大的数的索引q，因为p+1以后的数组都是排好序的。