题目描述
思路解析
一句话答案：LeetCode 31 下一个排列的标准解是三步法：从右往左找到第一个满足 nums[i] < nums[i+1] 的位置，在它右侧的降序后缀里从右往左挑刚好比它大的数交换，再把后缀反转成升序，就得到字典序上刚好更大的排列；若数组已完全降序则整体反转成最小排列。原地交换，时间 O(n)、空间 O(1)。
这道题真正在问什么
把数组原地重排成字典序里紧挨着它、刚好更大的那个排列，比如 [1,2,3] 的下一个是 [1,3,2]；如果它已经是这些数字的最大排列（完全降序，如 [3,2,1]），就回绕成最小排列（升序）。「刚好更大」四个字是全部难点：让排列变大很容易，让它变大得最少，才需要把排列的结构想清楚。
为什么从右往左找第一个升序对
想让一个数变大又涨幅最小，改动的位置应该尽量靠右——就像给数字加一要先动个位。从最右端往左看，只要相邻两数还是降序的，这一段就已经是这些数字能排出的最大值，在这段内部怎么折腾都变不大。第一个出现 nums[i] < nums[i+1] 的位置，就是从右数第一个「还有抬高余地」的位：它右边整段降序、已经到顶，所以下一个排列必须在这一位动手，且它左边的全部保持不动——若去动更左的位，跨过的排列就不止一个，得到的不再是「下一个」。
交换的对象为什么是刚好大一点的数
既然要抬高这一位，就得从它右边的后缀里挑一个比它大的数换上来；而为了整体「刚好更大」，要挑比它大的数里最小的那个。后缀恰好是降序的，所以从最右端往左遇到的第一个大于 nums[i] 的数就是目标，把两者交换即可。有重复元素时要注意判断的边界：查找时遇到小于等于 nums[i] 的都继续往左，保证不会选中相等的数——换一个相等的数等于没变大，排列原地踏步。
为什么交换之后还必须反转后缀
交换只完成了「抬高变动位」这半件事，此刻后缀仍是降序——换上去和换下来的两个数在大小上正好卡在原位的邻居之间，插回去不破坏降序——也就是说后缀还停在它的最大排列上。而我们要的是所有比原排列大的排列中最小的那个：变动位左边不动、变动位已定，后缀就应该取最小排列，即升序。后缀既然已是降序，用头尾双指针原地反转一遍就变成升序，这一步用 O(n) 的反转替代了排序，空间也保持 O(1)。
复杂度与三个常见翻车点
三个步骤各是一趟线性扫描或反转，时间 O(n)；全程只用几个下标原地交换，空间 O(1)。最常见的错：一是交换后忘了反转后缀，得到的排列比原来大得多、不是「下一个」；二是整个数组已完全降序、找不到升序对时，忘了把整体反转成升序而直接返回原数组；三是有重复元素时把第一步的判断写成严格大于就停，在相等处误停会选错位置——相等也要继续往左找。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这条「从右找第一个变小的位 i、和它右边刚好比它大的数换、再把 i 后面升序排（反转）」，下面每帧都在套它。
第①步从右往左检查相邻对：下标 7 的值 3 不小于右邻下标 8 的 2（还是降的）。降序说明这一段已经排到最大，没法在这里变大，继续往左找。
第①步从右往左检查相邻对：下标 6 的值 5 不小于右邻下标 7 的 3（还是降的）。降序说明这一段已经排到最大，没法在这里变大，继续往左找。
第①步从右往左检查相邻对：下标 5 的值 6 不小于右邻下标 6 的 5（还是降的）。降序说明这一段已经排到最大，没法在这里变大，继续往左找。
第①步从右往左检查相邻对：下标 4 的值 7 不小于右邻下标 5 的 6（还是降的）。降序说明这一段已经排到最大，没法在这里变大，继续往左找。
第①步从右往左检查相邻对：下标 3 的值 8 不小于右邻下标 4 的 7（还是降的）。降序说明这一段已经排到最大，没法在这里变大，继续往左找。
第①步从右往左检查相邻对：下标 2 的值 9 不小于右邻下标 3 的 8（还是降的）。降序说明这一段已经排到最大，没法在这里变大，继续往左找。
第①步从右往左检查相邻对，走到下标 1 与 2：nums[1]=4 比右边的 9 小，这是从右数第一个「升序对」！它的左数下标 i=1 就是我们要变大的那一位。停止扫描。
锁定 i=1（值 4）。它右边下标 2 到 8（绿色）是一整段降序后缀，已经是这些数能排出的最大值。所以要让整体变大，只能抬高 i 这一位。
第②步从最右往左找比 nums[i]=4 大的数：下标 8 的 2 还不够大（≤ nums[i]），标灰排除、继续往左。
第②步从最右往左找比 nums[i]=4 大的数：下标 7 的 3 还不够大（≤ nums[i]），标灰排除、继续往左。
第②步又从最右往左找：下标 6 的值 5 大于 nums[i]=4，这就是后缀里「刚好比 nums[i] 大」的数（因为后缀降序，从右数第一个超过它的，增幅最小）。锁定 j=6，停止。
锁定 j=6（值 5），它是后缀里刚好比 nums[i]=4 大一点的数。准备把下标 i=1（值 4）与下标 j=6（值 5）交换，让最高变动位抬高得尽量少。
交换完成：下标 1 变成 5，下标 6 变成 4（两个绿格）。最高变动位已经比原来大了，但右边的后缀此刻还是降序、偏大，接下来要把它压到最小。
第③步：交换后，下标 2 到 8 这段后缀（绿色）仍然是降序、是它能排的最大。我们要的是「刚好大一点」，所以把这段反转成升序，让后缀变成最小，增幅才最小。
反转用双指针从两端向中间：交换下标 2（值 9）和下标 8（值 2）。
换好了：下标 2 现在是 2，下标 8 现在是 9。两个指针各向中间收一格，继续反转剩下的部分。
反转用双指针从两端向中间：交换下标 3（值 8）和下标 7（值 3）。
换好了：下标 3 现在是 3，下标 7 现在是 8。两个指针各向中间收一格，继续反转剩下的部分。
反转用双指针从两端向中间：交换下标 4（值 7）和下标 6（值 4）。
换好了：下标 4 现在是 4，下标 6 现在是 7。两个指针各向中间收一格，继续反转剩下的部分。
后缀已经从降序翻成升序、取到最小。整个数组就是字典序里紧挨着原来、刚好比它大的下一个排列：[1, 5, 2, 3, 4, 6, 7, 8, 9]。三步从右扫 + 一次反转，O(n) 时间、O(1) 额外空间。
边界先想清：完全降序回到升序、单元素不变、有重复时第①步用 >= 才不会误停。
两个高频追问：朴素枚举 O(n!) 为何不可取，以及第①步为什么停在第一个升序对就最优。
参考代码
def nextPermutation(nums): n = len(nums) i = n - 2 while i >= 0 and nums[i] >= nums[i+1]: # ① 从右找第一个变小的位 i i -= 1 if i >= 0: j = n - 1 while nums[j] <= nums[i]: # ② 从右找刚好比 nums[i] 大的 j j -= 1 nums[i], nums[j] = nums[j], nums[i] # 交换 lo, hi = i + 1, n - 1 # ③ 反转 i 后面的后缀 while lo < hi: nums[lo], nums[hi] = nums[hi], nums[lo] lo += 1; hi -= 1复杂度
- 时间：O(n)，最坏扫两遍 + 反转一遍，都是线性
- 空间：O(1)，只用 i/j/lo/hi 几个下标，原地交换
易错点
面试追问把动画讲成自己的话
追问不用三步法，最朴素的解法是什么？为什么不可取？
追问为什么第①步停在「第一个升序对」就一定对？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
和为 K 的子数组
LeetCode 560 · 中等 · 沿着 数组 & 哈希 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题