下载掌阅APP，畅读海量书库
立即打开
将数字重新排列为下一个更大排列。如果无法进行这种排列，则必须将其重新排列为最小排列（即升序排列）。例如（输入在左列，其相应的输出在右列）：
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以后的数组都是排好序的。