31. 下一个排列

题目描述

整数数组的一个排列，就是将数组中的所有成员以序列形式排列。

数组的下一个排列是其所有排列中字典序刚好更大的那个排列。如果不存在更大的排列，则将数组重新排列为字典序最小的排列，也就是升序排列。

要求必须原地修改数组，并且只能使用常数额外空间。

示例：

输入：nums = [1, 2, 3]
输出：[1, 3, 2]

输入：nums = [3, 2, 1]
输出：[1, 2, 3]

输入：nums = [1, 1, 5]
输出：[1, 5, 1]

1. 什么是“字典序刚好更大”

比较两个等长数组时，从左向右找到第一个不同的位置，该位置元素较大的数组字典序更大。

因此，要找到下一个排列，需要同时满足：

新排列必须比当前排列大。
增大的幅度必须尽可能小。

为了让变化尽量小，应尽可能保留左侧的高位不变，从靠右的位置开始寻找可以增大的数字。找到后，还要让它只增大到最接近的更大值，并将其右侧排列成最小顺序。

最终得到三个步骤：

从右向左找第一个升序对
        -> 用后缀中刚好更大的数替换
        -> 将后缀调整为最小的升序

2. 第一步：寻找枢轴

从右向左寻找第一个满足下列条件的下标 pivot：

nums[pivot] < nums[pivot + 1]

代码写成：

let pivot = nums.length - 2;

while (pivot >= 0 && nums[pivot] >= nums[pivot + 1]) {
  pivot--;
}

循环结束后，pivot + 1 到数组末尾一定是一个非递增序列。

为什么要找最靠右的枢轴？

如果修改更靠左的位置，字典序会增加得更多。
非递增后缀已经是这些元素能形成的最大排列，只调整后缀无法得到更大的排列。
所以 pivot 是必须改变的最靠右位置，也就是让整体变化最小的起点。

例如：

nums = [1, 3, 5, 4, 2]
            ^
          pivot = 1

后缀 [5, 4, 2] 非递增，仅重新排列该后缀无法得到比当前数组更大的结果，必须增大 nums[1] = 3。

3. 第二步：寻找刚好更大的数

如果 pivot >= 0，需要在右侧后缀中找到一个比 nums[pivot] 大、但尽可能小的元素。

由于后缀是非递增序列，从数组末尾向左找到的第一个大于 nums[pivot] 的元素，恰好就是后缀中最小的较大值：

let successor = nums.length - 1;

while (nums[successor] <= nums[pivot]) {
  successor--;
}

然后交换二者：

[nums[pivot], nums[successor]] = [nums[successor], nums[pivot]];

继续上面的例子：

原数组：       [1, 3, 5, 4, 2]
枢轴：             ^
后缀中刚好更大：         ^  4
交换后：       [1, 4, 5, 3, 2]

这里不能随便选择一个更大的数。例如选择 5 会得到以 [1, 5] 开头的排列，显然比以 [1, 4] 开头的排列更大，不是紧邻的下一个排列。

4. 第三步：反转后缀

交换完成后，pivot 位置已经实现了最小幅度的增大。为了让整个排列尽可能小，需要把 pivot 右侧的元素排列成升序。

原后缀是非递增的，交换后仍保持非递增关系，因此只需使用双指针原地反转：

let left = pivot + 1;
let right = nums.length - 1;

while (left < right) {
  [nums[left], nums[right]] = [nums[right], nums[left]];
  left++;
  right--;
}

示例继续：

交换后：       [1, 4, 5, 3, 2]
反转后缀：     [1, 4, 2, 3, 5]

最终 [1, 4, 2, 3, 5] 就是 [1, 3, 5, 4, 2] 的下一个排列。

这里使用反转而不是排序，既利用了后缀已有的单调性，也满足 O(1) 额外空间的要求。

5. 完整示例推演

以 nums = [2, 3, 1, 3, 3] 为例，其中包含重复元素：

寻找枢轴

从右向左检查：

3 >= 3，继续向左
1 < 3，找到 pivot = 2

此时：

[2, 3, 1, 3, 3]
       ^  后缀 [3, 3] 非递增

寻找后继并交换

从末尾开始，第一个大于 1 的元素是最后一个 3：

交换前：[2, 3, 1, 3, 3]
交换后：[2, 3, 3, 3, 1]

反转后缀

反转 pivot + 1 之后的 [3, 1]：

[2, 3, 3, 1, 3]

这就是原排列的下一个排列。严格使用 > 寻找后继，可以正确跳过与枢轴相等的元素。

6. 代码实现

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function (nums) {
  let pivot = nums.length - 2;

  // 1. 找到最靠右的、可以被增大的位置。
  while (pivot >= 0 && nums[pivot] >= nums[pivot + 1]) {
    pivot--;
  }

  // 2. 用后缀中最小的较大值替换枢轴。
  if (pivot >= 0) {
    let successor = nums.length - 1;

    while (nums[successor] <= nums[pivot]) {
      successor--;
    }

    [nums[pivot], nums[successor]] = [nums[successor], nums[pivot]];
  }

  // 3. 将后缀从最大排列反转成最小排列。
  let left = pivot + 1;
  let right = nums.length - 1;

  while (left < right) {
    [nums[left], nums[right]] = [nums[right], nums[left]];
    left++;
    right--;
  }
};

7. 正确性说明

算法得到的一定是下一个排列，可以分三点证明：

结果更大：当存在枢轴时，将 nums[pivot] 换成了一个严格更大的元素，而枢轴左侧完全不变，所以新排列字典序严格更大。
增大的高位最靠右：枢轴右侧原本是最大排列，仅改变这段后缀无法使整体变大。因此，pivot 是能够增大整体的最靠右位置，所有改变更靠左位置的方案都会更大。
在该高位下增量最小：后继是后缀中最小的较大值；交换后又将后缀变为升序，即剩余元素的最小排列。因此不存在介于原排列与结果之间的其他排列。

如果找不到枢轴，整个数组就是非递增的，已经是字典序最大排列。将它反转后得到升序数组，正好是题目要求的最小排列。

8. 复杂度分析

时间复杂度：O(n)。寻找枢轴、寻找后继和反转后缀分别最多扫描一次数组。
空间复杂度：O(1)。所有交换都在原数组上完成，只使用常数个变量。

9. 边界条件与易错点

边界条件：

数组只有一个元素时，pivot 初始为 -1，反转区间为空，数组保持不变。
数组整体非递增时不存在更大的排列，应反转整个数组得到最小排列。
数组整体严格递增时，枢轴是倒数第二个元素，只需交换最后两个元素。
数组可以包含重复元素，比较符号必须正确处理相等情况。

易错点：

寻找枢轴时应跳过 nums[pivot] >= nums[pivot + 1]，相等也不能构成可增大的位置。
寻找后继时需要严格满足 nums[successor] > nums[pivot]，不能选择相等元素。
必须从右向左找后继；后缀非递增，最右边满足条件的元素才是最小的较大值。
交换之后要反转 pivot + 1 到末尾，而不是从 pivot 开始。
即使没有找到枢轴，也必须执行反转，此时反转范围是整个数组。
题目要求原地修改，不需要也不应依赖返回一个新数组。

10. 常见错误方案

生成全部排列后排序

这种方法不仅实现复杂，还需要生成最多 n! 个排列，时间和空间开销都远超要求，也没有利用当前排列局部的单调结构。

交换后不整理后缀

仅交换枢轴和后继只能保证结果变大，不能保证它是最接近的更大排列。后缀必须变为升序，才能让低位取到最小值。

对后缀调用 `sort`

排序能够得到正确答案，但需要 O(n log n) 时间，而且排序实现可能使用额外空间。原后缀已经非递增，直接反转即可在线性时间内得到升序。

11. 面试追问

为什么交换后后缀仍然非递增？

后继是从右向左找到的第一个大于枢轴的元素。它右侧的元素都小于等于原枢轴；交换后，原枢轴被放到后继位置，因此它仍然大于等于右侧元素。同时，它左侧原有元素与相邻关系不会破坏非递增顺序，所以整个后缀仍可直接反转。

如何求上一个排列？

操作完全对称：从右向左找第一个 nums[pivot] > nums[pivot + 1] 的位置；从末尾找第一个严格小于枢轴的元素并交换；最后反转后缀，使其变为降序，从而得到字典序刚好更小的排列。

为什么这题不是普通的排列回溯？

题目不是要求生成所有排列，而是利用当前排列直接计算它的字典序后继。回溯会枚举大量无关排列，而本算法只扫描并调整必要的后缀。

12. 可迁移总结

下一个排列的核心是“高位最晚变化、变化幅度最小、低位取最小值”：

找最靠右的可增大位置
  -> 换成刚好更大的值
    -> 剩余位置排列成最小状态

当题目要求在字典序、数值或状态序列中找到“严格更大但最接近”的结果时，可以沿用这种思考方式：先确定最靠后的可变位置，再做最小幅度修改，最后把其余低位重置为最小状态。

#31. 下一个排列

#题目描述

#1. 什么是“字典序刚好更大”

#2. 第一步：寻找枢轴

#3. 第二步：寻找刚好更大的数

#4. 第三步：反转后缀

#5. 完整示例推演

#寻找枢轴

#寻找后继并交换

#反转后缀

#6. 代码实现

#7. 正确性说明

#8. 复杂度分析

#9. 边界条件与易错点

#10. 常见错误方案

#生成全部排列后排序

#交换后不整理后缀

#对后缀调用 sort

#11. 面试追问

#为什么交换后后缀仍然非递增？

#如何求上一个排列？

#为什么这题不是普通的排列回溯？

#12. 可迁移总结