31. 下一个排列
难度：中等 | 主题：数组 + 双指针
题目
整数数组的一个排列就是将其所有成员以序列或线性顺序排列。下一个排列是指下一个字典序更大的排列。给你一个整数数组 nums，找出 nums 的下一个排列。如果不存在下一个更大的排列，则将数组重新排列为最小的排列（即升序排列）。必须原地修改。
示例
输入：nums = [1,2,3]
输出：[1,3,2]
解释：123 的下一个排列是 132
思路
先讲个故事：电子密码锁
你有一个电子密码锁，密码是四位数。你随手拨到 21543，想看看”下一个有效密码”是什么。
你盯着数字想了想：
-
从右往左找”下降点”——5→4→3 都在增大（降序），直到 1→5 这里变小了。1 就是进位点。
-
从右往左找比 1 大的最小的数——3（因为 3 > 1 且比 5 和 4 更接近 1）。交换 1 和 3，得到 23541。
-
进位点右边的部分（541），现在是降序，反转成升序（145）→ 得到 23145。
21543 的下一个密码是 23145。
这就是”下一个排列”算法的本质——找进位点 → 进位 → 后面归零最小化，和数字进位的思维一模一样。
引导式推导：三步标准算法
理解”字典序下一个”
全排列按字典序排列：[1,2,3] → [1,3,2] → [2,1,3] → [2,3,1] → [3,1,2] → [3,2,1] → 回到 [1,2,3]
要找到”刚好比当前大的下一个”，不能跳（排序后不一定比当前大 1），也不能回到开头。
核心洞察：类比数字进位
拿 21543 举例：
-
最后四位 1543 是递减的——这是”尾部最大”的状态（降序是最大的排列方式）
-
要想变大，必须动到倒数第 5 位（1），因为 1543 已经最大，无法再增
-
找到”进位点”（从右往左第一个下降的点）
graph TD subgraph SGlirsj["21543 -> 23145"] step1["① 找下降点: 1 < 5 -> 进位点在 1"] step2["② 找交换对象: 从右找第一个 > 1 -> 3"] step3["③ 交换 1 和 3: 23541"] step4["④ 反转 5 4 1 -> 1 4 5: 23145"] end step1 --> step2 --> step3 --> step4
为什么反转？
交换后，原进位点右边的部分仍然是降序（因为交换没有破坏降序性质——被交换的元素本来就在降序序列中最接近）。降序是”这段能组成的最大排列”，我们需要的是”最小的下一个”→ 反转成升序。
如果没有下降点？
整个数组是降序（如 [3,2,1]）→ 这是最大排列→ 下一个回到最小→ 反转整个数组。
代码
def nextPermutation(self, nums):
n = len(nums)
i = n - 2
# ① 从右往左找第一个下降点：nums[i] < nums[i+1]
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0: # 找到了下降点（不是最大排列）
# ② 从右往左找第一个严格大于 nums[i] 的数
j = n - 1
while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i] # ③ 交换
# ④ 反转 i+1 到末尾（无条件执行：最大排列时反转整个数组）
left, right = i + 1, n - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
复杂度
| 指标 | 值 | 解释 |
|---|---|---|
| 时间 | O(n) | 最坏扫描两遍 + 反转一遍，三个循环是加法关系 |
| 空间 | O(1) | 原地修改 |
实战考量
频率分析
出现在：字节/美团/阿里 二面，考察数学规律和步骤拆分能力。难在”你想不到这三步”而不是”这三步写不出来”。很多人知道思路但写不对边界条件。
延伸思考
Q：上一个排列怎么做？
A：反过来：找上升点（nums[i] > nums[i+1]）→ 从右找更小的交换 → 反转后面变降序。
Q：第 k 个排列怎么求？
A：用阶乘确定每一位的数字。不需要逐个求到第 k 个。n=4，k=9，第一位是 9/3! = 1…3，索引 1 的元素（2），然后在剩下的数字中继续。详见 60 题。
Q：为什么反转是”无条件执行”的？
A：如果 i = -1（整个数组降序，没有找到下降点），反转整个数组就是”最大排列变最小排列”。统一处理。
Q：找交换对象时为什么用 <= 而不是 <？
A：相等时交换无意义（得到同样的排列），要找严格大于 nums[i] 的数。
易错点
-
反转无条件执行——不管有没有找到下降点都要反转
-
while nums[j] <= nums[i]用<=而非< -
三个循环依次执行，时间相加不是相乘
-
下降点的索引范围是 n-2 到 0
生活类比
下一个排列 → 找进位点 → 进位 → 归零最小化
像你手机上的数字时钟从 23:59:59 跳到 00:00:00：
秒数到了 59（最大）→ 归零，分钟进一 → 分钟也到了 59 → 归零，小时进一。
下一个排列也是一样的逻辑：从右往左找到”还能变大的那一位”（下降点），把它变大一点点（交换），后面所有位”归零”到最小（降序变升序）。
如果所有位都不能变大了 → 全部归零，回到起点。
相关题目
→ 返回题单：LeetCode学习路线图 > 一、数组与哈希（含双指针、矩阵）
速记卡（面试闪卡）
Q1：一句话讲清「31. 下一个排列」到底是什么？
A：下一个排列是找字典序刚好比当前大的排列：找下降点→交换→反转尾部，原地 O(n) 完成。
Q2：像什么生活场景 —— 怎么理解？
A：像电子密码锁拨到 21543，想看「下一个有效密码」：从右找下降点 1（进位点），从右找比它大的最小数 3 交换，右边降序反转成升序，得 23145。
Q3：三步标准算法 —— 怎么理解？
A：像数字进位：①从右找第一个下降点 nums[i]<nums[i+1]；②从右找第一个>nums[i] 交换；③反转 i+1 到末尾。反转无条件执行，最大排列时反转整组即回到最小。
Q4：复杂度与易错点 —— 怎么理解？
A：像扫地扫两遍：时间 O(n)（扫描两遍+反转，加法关系），空间 O(1) 原地。易错：反转无条件、找对象用 <= 而非 <、下降点索引范围 n-2 到 0。
Q5：延伸与变体 —— 怎么理解？
A：像同一套锁芯换方向：上一个排列反过来（找上升点→找更小交换→反转变降序）；第 k 个排列用阶乘定位每一位，不必逐个求。字节 / 美团二面常考步骤拆分。
Q6：核心速记主线有哪些？
-
字典序下一个：下降点→交换→反转
-
反转无条件，最大排列即归零
-
时间 O(n) 空间 O(1) 原地
-
找对象用 <=，下降点 n-2 到 0
口诀
A：下一个排列找下降，进位交换反转尾
反转无条件莫忘，最大归零回起点
时间 O n 空间一，原地改动不费地
上一个反过来求，阶乘定位第 k 位