1. 打开题目之前先把“字典序”这层窗户纸捅破LeetCode 31这道题题面短得可怜实现获取“下一个排列”的函数算法需要将给定数字序列重新排列成字典序中下一个更大的排列如果不存在下一个更大的排列则将数字重新排列成最小的排列即升序排列。要求原地修改只允许使用额外常数空间。我第一次刷这道题的时候第一次看题想了半天什么叫“字典序中下一个更大的排列”——示例给的是[1,2,3] → [1,3,2][3,2,1] → [1,2,3][1,1,5] → [1,5,1]。这三个例子看完感觉好像懂了又好像什么都没懂。真正的分水岭在于你得先搞明白“字典序”这三个字在这个场景下到底是什么意思否则后面所有代码都是抄完就忘。字典序本质上就是“把排列当成一个数字来比较大小”的规则。拿[1,2,3]来说它组成的数字是 123[1,3,2]是 132[2,1,3]是 213。从小到大排123 132 213 231 312 321这正好是所有1、2、3三个元素能组成的全部 3! 6 个排列的排序结果。题目里说的“下一个排列”就是要求你求出“比当前这个数字大一点点”的那个排列注意是“大一点点”不是大很多。这个“大一点点”非常关键。比如当前排列是 123下一个是 132而不是 213当前是 132下一个是 213。也就是说你每次要做的是在所有比当前排列大的排列里挑一个最小的出来。如果是全排列的最后一个比如 321那就绕回起点变成 123。换个生活化的比喻你把字典里所有单词按字母顺序排好“排列”和“排列组合”这两个词按字典序是相邻的从一个词到下一个词改动永远是尽量靠右、尽量小的一刀。这个感觉刷这道题之前一定要找到。理解了这一点再看题目其实就一句话给一个排列求它在全排列字典序里的下一个邻居。理解了需求你才有资格谈解法否则看答案都看不出哪一步在干嘛。2. 为什么暴力解法不省心全排列是万万不能真的全部列出来的很多第一次刷题的人包括我自己第一反应是把所有排列全列出来排序找到当前排列的下一个。理论上完全正确实际上直接爆炸。举个例子数组长度 n那排列总数是 n!。n 10 的时候就是 3,628,800 个排列内存和时间还能勉强接受n 12 就是 479,001,600 个快 5 亿个排列等你 n 15那就是 1.3 万亿个排列。而 LeetCode 31 的约束里 n 最大可以到 100100 的阶乘是 9.33×10^157宇宙原子总数才 10^80 级别——这个数量级你算到宇宙热寂也算不完。暴力枚举这条路思路简单但复杂度完全不可接受它只适合你在草稿纸上验证小规模数据时用用。所以这道题真正考察的不是“你会不会枚举”而是“你能不能不枚举直接从当前排列的结构里推导出下一个排列是什么”。这背后是一种非常典型的“找规律 贪心”的算法思想。先抛开代码拿一个具体例子来观察规律。假设当前排列是[6, 8, 7, 4, 1]肉眼来看下一个排列应该是什么样的第一步你要找到“从右往左看第一次出现升序的那一对相邻元素”。什么意思从最右边往左边走1和4比1 4这是降序4和7比4 7还是降序7和8比7 8还是降序8和6比8 6出现了升序找到了这对元素是6和8我们把位置记下来6的下标是 i 0。这个6就是我们后面要动刀的地方。第二步再在6右边的子数组[8, 7, 4, 1]里从右往左找第一个比6大的元素。1 6不行4 6不行7 6二可以找到了7。把6和7交换得到[7, 8, 6, 4, 1]。第三步把i之后的子数组也就是8, 6, 4, 1反转。反转后变成[7, 1, 4, 6, 8]。这就是答案。你也许心里狐疑为什么这样操作就对了这里面每一步背后都藏着严密的逻辑下一节我们慢慢地、一层一层地拆开揉碎。3. 从右往左扫描这三步为什么顺序一步都不能乱3.1 寻找那个“决定命运”的下标 i它标记的是最后一个“还能变大”的位置先从直观的层面理解一下“从右往左找第一个升序对”。一个排列如果要变大只能把某个较大的数字往前提、把较小的数字往后放而为了让“变大”的幅度尽量小你这个“动刀”的位置一定要尽量靠右。举例说明[6, 8, 7, 4, 1]的最后一个片段7, 4, 1是严格递减的它内部的任何局部调整都不可能让它变大——因为把最后三位换个顺序最大也就是[6, 8, 7, 4, 1]本身。想要更大必须动到6这个位置把6换成右边某个比它大的数整个排列一下子就变大了。而6恰好是“从右往左看第一个比右侧邻居小的元素”它就是“最后一个还能让排列变大”的位置。这个 i 的定位是整个算法的灵魂。找到它你就能保证i 右侧的所有元素构成的是一个从右往左看单调递增也就是从左往右看单调递减的序列它已经是“这一后缀能组成的最大排列”不可能在内部变大只能动 i。3.2 在右边找到“刚好比 a[i] 大一点”的元素这是贪心策略的精确落点确定 i 之后i 右边是降序排列的但其中每个元素都比 a[i] 大吗不一定。[6, 8, 7, 4, 1]里 i 0右边有8 6、7 6但也有4 6、1 6。如果你随便换一个比 6 大的比如把 6 和 8 换得到[8, 6, 7, 4, 1]这个确实是变大了但它不是“最小的大”——把 6 和 7 换得到的[7, 8, 6, 4, 1]显然更小而且仍然比原排列大。贪心就贪心在交换进来的那个元素要“刚刚好”比 a[i] 大。为了做到这一点你要在 i 右侧的降序序列里从右往左找到第一个大于 a[i] 的元素——因为右边从右往左是递增的第一个扫到的大于 a[i] 的元素恰好就是所有大于 a[i] 的元素里最小的那个。这一步也再一次保证了“下一个”的“下”字能得到落实。3.3 交换之后把 i 右侧整体反转让后缀变成最小排列交换完之后i 右侧的元素依然保持降序比如从[7, 8, 6, 4, 1]这个中间态来看8, 6, 4, 1还是降序的。但问题来了我们已经抬高了 i 位置上的数字后缀部分现在是降序的最大形态而我们要的是“下一个”排列后缀应当处于它可能的最小形态才能保证整体尽可能小。升序排列是所有排列中最小的所以把后缀整个反转成升序就得到了当前抬升之后的最小后缀组合。而且由于交换时选的是“最小的大于 a[i] 的元素”所以交换之后右侧序列从右往左看仍然是严格的递增关系也就是反转之后正好是全局升序不需要再排序一次 reverse 就完事。这一步如果写成 sort也不会错但 O(n log n) 的复杂度不如 O(n) 的 reverse 干净属于能跑但没吃到精髓的写法。上面的一切都以“能找到一个严格大于 a[i] 的元素”为前提。如果从右往左扫完都没找到升序对说明整个排列已经是降序——它就是字典序里最大的那个排列此时按题目要求直接整体反转回到最小排列。这个边界情况千万别漏掉。4. 完整实现与代码细节一步到位不留死角和隐藏雷区清晰了算法流程之后代码写起来就非常直白了。下面给出 C 实现这也是面试时最常写的版本。#include vector #include algorithm using namespace std; class Solution { public: void nextPermutation(vectorint nums) { int n nums.size(); int i n - 2; // 从倒数第二个位置开始向前找 // 1. 从右向左找到第一个升序对 (nums[i] nums[i1]) while (i 0 nums[i] nums[i 1]) { i--; } // 2. 如果找到了升序对在右侧找一个最小的大于 nums[i] 的数并交换 if (i 0) { int j n - 1; while (j 0 nums[j] nums[i]) { j--; } swap(nums[i], nums[j]); } // 3. 将 i 右侧的部分反转使其成为升序若 i -1则整体反转 reverse(nums.begin() i 1, nums.end()); } };是不是短得惊人核心逻辑一共就三个 while/if 加一个 reverse。但越是这种短代码越要注意细节能不能写准。首先是找 i 的循环条件nums[i] nums[i 1]这里用的是而不是。为什么要包含等于的情况因为如果存在重复元素比如[1, 5, 1]从右往左看1和5比较1 5那 i 直接定位到 1 的下标 0这没问题。但如果数组是[1, 5, 5]从右往左看第一个比较是nums[1] 5和nums[2] 5两者相等。相等时继续向左移动直到出现严格小于右侧的相邻元素nums[0] 1 nums[1] 5所以 i 0。这里如果没用而用了相等的情况就会被误当成“升序对”处理于是 i 会停在 1 的位置结果就完全错了。这是一道经典的边界陷阱刷题的时候非常容易翻车。再来看第二步找 j 的循环while (j 0 nums[j] nums[i]) j--;。这里的同样有讲究。交换的目的是找一个“最小的大于 a[i]”的元素如果我们用了遇到相等的元素时就不会继续左移会停在那个相等的元素上。但交换相等的元素没有任何意义还会破坏排列的结构。举个例子[1, 4, 2, 2]i 定位在 1因为nums[1] 4 nums[2] 2不符合升序条件继续左移发现nums[0] 1 nums[1] 4。在右侧找大于 1 的元素时用会把 j 一路扫到最右侧的2停下然后交换 1 和 2得到[2, 4, 2, 1]再反转后缀得到[2, 1, 2, 4]。如果用第一次扫到2下标 2就停了直接交换 1 和 2得到[2, 4, 1, 2]反转后缀后是[2, 2, 1, 4]这比正确答案[2, 1, 2, 4]要大显然不是“下一个排列”。所以第二个 while 里的正确写法对应的是“取最右侧的、刚好大于 a[i] 的元素”这也是去重逻辑在本题中的体现。换一种语言Python 版本会更简短但逻辑一模一样from typing import List class Solution: def nextPermutation(self, nums: List[int]) - None: n len(nums) i n - 2 while i 0 and nums[i] nums[i 1]: i - 1 if i 0: j n - 1 while j 0 and nums[j] nums[i]: j - 1 nums[i], nums[j] nums[j], nums[i] left, right i 1, n - 1 while left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1Python 里可以直接nums[i1:] reversed(nums[i1:])但手写双指针反转可以避免额外空间开销的讨论面试时更保险。代码本身难度不高真正让这道题有分量的是你能否在写完代码后把每一步的“为什么”说得清楚。下面这张表把我平时面试时最常追问的三个点整理了出来细节常见错误写法正确写法原因找 i 的循环条件nums[i] nums[i1]nums[i] nums[i1]相等时继续左移避免把相等元素误当升序对找 j 的循环条件nums[j] nums[i]nums[j] nums[i]跳过相等元素选取最右侧的“刚好大于 a[i]”的元素找不到 i 时的处理直接返回reverse整体当前排列已是最大排列按题意需要返回最小排列反转后是否还需要排序sort(nums.begin()i1, nums.end())reverse(nums.begin()i1, nums.end())交换后右侧仍保持降序反转即为升序sort 是多余且更慢的做法5. 从 LeetCode 31 延伸出去一组同源的排列算法变体与使用场景刷过 LeetCode 31 之后你会发现这是一个“母题”很多看似不相干的题内核都是“下一个排列”的变体。最有名的就是 LeetCode 556“下一个更大元素 III”——给你一个正整数 n让你调换它的各位数字得到大于 n 的最小整数不存在则返回 -1。这道题本质就是把正整数拆成数字数组先做一遍“下一个排列”然后检查结果是否还在 int 范围内。我当年刷到 556 时第一反应是“这题跟 31 有啥关系”把 31 的代码搬过来之后发现几乎不用改只需要处理两个额外事项一是把输入整数先转成数组二是做完 nextPermutation 之后判断一下结果的首位是不是 0如果原数位数相同首位不能是 0。这个迁移过程比你自己从零想一个解法快得多也稳得多。再往远处看“下一个排列”的思路在全排列生成算法字典序法里也是核心。LeetCode 46“全排列”如果你用标准库的next_permutation来做背后的实现就是这道题的逻辑。很多 C 选手天天用std::next_permutation却不知道它内部就是这段“从右往左找升序对、交换、反转”的流程。弄懂了 LeetCode 31你就等于把标准库一个高频功能的内幕彻底看穿了。排序算法里也会用到类似“从右往左扫描找逆序对”的结构。比如冒泡排序每轮会把最大值“冒”到最右边这个从右往左或者从左往右扫描的过程和你找 i 的过程在思路上有相通之处——都是在局部序列里寻找顺序关系的破坏点。虽然它们解决的问题不同但“扫描方向 相邻比较”这个组合是很多数组操作题的共性骨架。贪心算法就更不用说了。找 j 的过程就是一个典型的贪心选择在候选集里挑一个最优的元素。很多人觉得贪心抽象但放到这个场景里目标明确最小的更大数约束清晰右侧降序贪心策略就变得非常自然。所以我一直觉得LeetCode 31 是一道“性价比”极高的题。它代码短、边界多、思想深、延伸广。你花一个下午把它彻底吃透后面遇到 556、46、47甚至某些排列相关的回溯题都能省不少力气。6. 我踩过的坑和总结出的判断口诀最后说几个我自己刷这道题时踩过、也见证过别人踩的坑以及一个可以让你少走弯路的判断口诀。第一个坑是“从右往左找升序对”这个方向搞反。新手第一次写特别容易写成从左往右找第一个降序对。方向一反整个算法全乱。你只要记住一句话右边的数字已经处于“最大形态”降序时它是不能内部变大的一定要从更左边借一个数字来“抬升”。所以扫描必须从右往左找到的第一个升序对就是最后一个还能变大的位置。第二个坑是第二步“交换之后直接 reverse 右侧”时有人会想右侧不一定是升序啊是不是得先 sort我当时也犹豫过后来想明白了因为你在右侧找 j 时取的是“最小的比 a[i] 大的元素”并且是从右往左扫的所以交换之后右侧依旧保持降序不变。降序直接反转必得升序完全不需要排序。这个“交换不破坏右侧降序”的性质是这道题最精妙的地方。第三个坑是重复元素。前面提到的和缺一个等号结果就错。刷题时如果测试用例带着重复元素特别容易翻车。建议你写完代码之后专门把[1, 5, 1]、[1, 4, 2, 2]、[2, 3, 1, 3, 3]这种带重复数字的用例手跑一遍比单纯背代码有效得多。第四个坑是“已经最大排列”的情况。比如[3, 2, 1]循环退出来 i -1这时候直接整体反转。很多人会忘记处理 i -1 的情况导致 reverse 起点不对或者越界。一个很简单的自查方法代码里reverse(nums.begin() i 1, nums.end())这个写法在 i -1 时正好是reverse(nums.begin(), nums.end())分毫不差。所以这个写法本身就是在帮你兜底。如果你想要一个快速记忆的口诀我自己的是一找升序对二挑最小大三换位四翻转。十二个字够你面试时在脑海里过一遍流程了。这道题刷完之后建议顺手做两道练习题巩固LeetCode 556下一个更大元素 III和 LeetCode 46全排列如果用了标准库试着关了它手写一遍。把排列生成与字典序这两个概念串起来你对“下一个排列”的理解就不会只是停留在背代码的层面而是真正内化成了算法直觉。以后不管是笔试、面试还是实际工程里碰到“按字典序生成所有方案”之类的需求这道题的思路都能直接迁移过去属于典型的“花一小时学会、吃十年老本”的题目。
LeetCode 31：字典序“下一个排列”的三步算法与代码实现
1. 打开题目之前先把“字典序”这层窗户纸捅破LeetCode 31这道题题面短得可怜实现获取“下一个排列”的函数算法需要将给定数字序列重新排列成字典序中下一个更大的排列如果不存在下一个更大的排列则将数字重新排列成最小的排列即升序排列。要求原地修改只允许使用额外常数空间。我第一次刷这道题的时候第一次看题想了半天什么叫“字典序中下一个更大的排列”——示例给的是[1,2,3] → [1,3,2][3,2,1] → [1,2,3][1,1,5] → [1,5,1]。这三个例子看完感觉好像懂了又好像什么都没懂。真正的分水岭在于你得先搞明白“字典序”这三个字在这个场景下到底是什么意思否则后面所有代码都是抄完就忘。字典序本质上就是“把排列当成一个数字来比较大小”的规则。拿[1,2,3]来说它组成的数字是 123[1,3,2]是 132[2,1,3]是 213。从小到大排123 132 213 231 312 321这正好是所有1、2、3三个元素能组成的全部 3! 6 个排列的排序结果。题目里说的“下一个排列”就是要求你求出“比当前这个数字大一点点”的那个排列注意是“大一点点”不是大很多。这个“大一点点”非常关键。比如当前排列是 123下一个是 132而不是 213当前是 132下一个是 213。也就是说你每次要做的是在所有比当前排列大的排列里挑一个最小的出来。如果是全排列的最后一个比如 321那就绕回起点变成 123。换个生活化的比喻你把字典里所有单词按字母顺序排好“排列”和“排列组合”这两个词按字典序是相邻的从一个词到下一个词改动永远是尽量靠右、尽量小的一刀。这个感觉刷这道题之前一定要找到。理解了这一点再看题目其实就一句话给一个排列求它在全排列字典序里的下一个邻居。理解了需求你才有资格谈解法否则看答案都看不出哪一步在干嘛。2. 为什么暴力解法不省心全排列是万万不能真的全部列出来的很多第一次刷题的人包括我自己第一反应是把所有排列全列出来排序找到当前排列的下一个。理论上完全正确实际上直接爆炸。举个例子数组长度 n那排列总数是 n!。n 10 的时候就是 3,628,800 个排列内存和时间还能勉强接受n 12 就是 479,001,600 个快 5 亿个排列等你 n 15那就是 1.3 万亿个排列。而 LeetCode 31 的约束里 n 最大可以到 100100 的阶乘是 9.33×10^157宇宙原子总数才 10^80 级别——这个数量级你算到宇宙热寂也算不完。暴力枚举这条路思路简单但复杂度完全不可接受它只适合你在草稿纸上验证小规模数据时用用。所以这道题真正考察的不是“你会不会枚举”而是“你能不能不枚举直接从当前排列的结构里推导出下一个排列是什么”。这背后是一种非常典型的“找规律 贪心”的算法思想。先抛开代码拿一个具体例子来观察规律。假设当前排列是[6, 8, 7, 4, 1]肉眼来看下一个排列应该是什么样的第一步你要找到“从右往左看第一次出现升序的那一对相邻元素”。什么意思从最右边往左边走1和4比1 4这是降序4和7比4 7还是降序7和8比7 8还是降序8和6比8 6出现了升序找到了这对元素是6和8我们把位置记下来6的下标是 i 0。这个6就是我们后面要动刀的地方。第二步再在6右边的子数组[8, 7, 4, 1]里从右往左找第一个比6大的元素。1 6不行4 6不行7 6二可以找到了7。把6和7交换得到[7, 8, 6, 4, 1]。第三步把i之后的子数组也就是8, 6, 4, 1反转。反转后变成[7, 1, 4, 6, 8]。这就是答案。你也许心里狐疑为什么这样操作就对了这里面每一步背后都藏着严密的逻辑下一节我们慢慢地、一层一层地拆开揉碎。3. 从右往左扫描这三步为什么顺序一步都不能乱3.1 寻找那个“决定命运”的下标 i它标记的是最后一个“还能变大”的位置先从直观的层面理解一下“从右往左找第一个升序对”。一个排列如果要变大只能把某个较大的数字往前提、把较小的数字往后放而为了让“变大”的幅度尽量小你这个“动刀”的位置一定要尽量靠右。举例说明[6, 8, 7, 4, 1]的最后一个片段7, 4, 1是严格递减的它内部的任何局部调整都不可能让它变大——因为把最后三位换个顺序最大也就是[6, 8, 7, 4, 1]本身。想要更大必须动到6这个位置把6换成右边某个比它大的数整个排列一下子就变大了。而6恰好是“从右往左看第一个比右侧邻居小的元素”它就是“最后一个还能让排列变大”的位置。这个 i 的定位是整个算法的灵魂。找到它你就能保证i 右侧的所有元素构成的是一个从右往左看单调递增也就是从左往右看单调递减的序列它已经是“这一后缀能组成的最大排列”不可能在内部变大只能动 i。3.2 在右边找到“刚好比 a[i] 大一点”的元素这是贪心策略的精确落点确定 i 之后i 右边是降序排列的但其中每个元素都比 a[i] 大吗不一定。[6, 8, 7, 4, 1]里 i 0右边有8 6、7 6但也有4 6、1 6。如果你随便换一个比 6 大的比如把 6 和 8 换得到[8, 6, 7, 4, 1]这个确实是变大了但它不是“最小的大”——把 6 和 7 换得到的[7, 8, 6, 4, 1]显然更小而且仍然比原排列大。贪心就贪心在交换进来的那个元素要“刚刚好”比 a[i] 大。为了做到这一点你要在 i 右侧的降序序列里从右往左找到第一个大于 a[i] 的元素——因为右边从右往左是递增的第一个扫到的大于 a[i] 的元素恰好就是所有大于 a[i] 的元素里最小的那个。这一步也再一次保证了“下一个”的“下”字能得到落实。3.3 交换之后把 i 右侧整体反转让后缀变成最小排列交换完之后i 右侧的元素依然保持降序比如从[7, 8, 6, 4, 1]这个中间态来看8, 6, 4, 1还是降序的。但问题来了我们已经抬高了 i 位置上的数字后缀部分现在是降序的最大形态而我们要的是“下一个”排列后缀应当处于它可能的最小形态才能保证整体尽可能小。升序排列是所有排列中最小的所以把后缀整个反转成升序就得到了当前抬升之后的最小后缀组合。而且由于交换时选的是“最小的大于 a[i] 的元素”所以交换之后右侧序列从右往左看仍然是严格的递增关系也就是反转之后正好是全局升序不需要再排序一次 reverse 就完事。这一步如果写成 sort也不会错但 O(n log n) 的复杂度不如 O(n) 的 reverse 干净属于能跑但没吃到精髓的写法。上面的一切都以“能找到一个严格大于 a[i] 的元素”为前提。如果从右往左扫完都没找到升序对说明整个排列已经是降序——它就是字典序里最大的那个排列此时按题目要求直接整体反转回到最小排列。这个边界情况千万别漏掉。4. 完整实现与代码细节一步到位不留死角和隐藏雷区清晰了算法流程之后代码写起来就非常直白了。下面给出 C 实现这也是面试时最常写的版本。#include vector #include algorithm using namespace std; class Solution { public: void nextPermutation(vectorint nums) { int n nums.size(); int i n - 2; // 从倒数第二个位置开始向前找 // 1. 从右向左找到第一个升序对 (nums[i] nums[i1]) while (i 0 nums[i] nums[i 1]) { i--; } // 2. 如果找到了升序对在右侧找一个最小的大于 nums[i] 的数并交换 if (i 0) { int j n - 1; while (j 0 nums[j] nums[i]) { j--; } swap(nums[i], nums[j]); } // 3. 将 i 右侧的部分反转使其成为升序若 i -1则整体反转 reverse(nums.begin() i 1, nums.end()); } };是不是短得惊人核心逻辑一共就三个 while/if 加一个 reverse。但越是这种短代码越要注意细节能不能写准。首先是找 i 的循环条件nums[i] nums[i 1]这里用的是而不是。为什么要包含等于的情况因为如果存在重复元素比如[1, 5, 1]从右往左看1和5比较1 5那 i 直接定位到 1 的下标 0这没问题。但如果数组是[1, 5, 5]从右往左看第一个比较是nums[1] 5和nums[2] 5两者相等。相等时继续向左移动直到出现严格小于右侧的相邻元素nums[0] 1 nums[1] 5所以 i 0。这里如果没用而用了相等的情况就会被误当成“升序对”处理于是 i 会停在 1 的位置结果就完全错了。这是一道经典的边界陷阱刷题的时候非常容易翻车。再来看第二步找 j 的循环while (j 0 nums[j] nums[i]) j--;。这里的同样有讲究。交换的目的是找一个“最小的大于 a[i]”的元素如果我们用了遇到相等的元素时就不会继续左移会停在那个相等的元素上。但交换相等的元素没有任何意义还会破坏排列的结构。举个例子[1, 4, 2, 2]i 定位在 1因为nums[1] 4 nums[2] 2不符合升序条件继续左移发现nums[0] 1 nums[1] 4。在右侧找大于 1 的元素时用会把 j 一路扫到最右侧的2停下然后交换 1 和 2得到[2, 4, 2, 1]再反转后缀得到[2, 1, 2, 4]。如果用第一次扫到2下标 2就停了直接交换 1 和 2得到[2, 4, 1, 2]反转后缀后是[2, 2, 1, 4]这比正确答案[2, 1, 2, 4]要大显然不是“下一个排列”。所以第二个 while 里的正确写法对应的是“取最右侧的、刚好大于 a[i] 的元素”这也是去重逻辑在本题中的体现。换一种语言Python 版本会更简短但逻辑一模一样from typing import List class Solution: def nextPermutation(self, nums: List[int]) - None: n len(nums) i n - 2 while i 0 and nums[i] nums[i 1]: i - 1 if i 0: j n - 1 while j 0 and nums[j] nums[i]: j - 1 nums[i], nums[j] nums[j], nums[i] left, right i 1, n - 1 while left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1Python 里可以直接nums[i1:] reversed(nums[i1:])但手写双指针反转可以避免额外空间开销的讨论面试时更保险。代码本身难度不高真正让这道题有分量的是你能否在写完代码后把每一步的“为什么”说得清楚。下面这张表把我平时面试时最常追问的三个点整理了出来细节常见错误写法正确写法原因找 i 的循环条件nums[i] nums[i1]nums[i] nums[i1]相等时继续左移避免把相等元素误当升序对找 j 的循环条件nums[j] nums[i]nums[j] nums[i]跳过相等元素选取最右侧的“刚好大于 a[i]”的元素找不到 i 时的处理直接返回reverse整体当前排列已是最大排列按题意需要返回最小排列反转后是否还需要排序sort(nums.begin()i1, nums.end())reverse(nums.begin()i1, nums.end())交换后右侧仍保持降序反转即为升序sort 是多余且更慢的做法5. 从 LeetCode 31 延伸出去一组同源的排列算法变体与使用场景刷过 LeetCode 31 之后你会发现这是一个“母题”很多看似不相干的题内核都是“下一个排列”的变体。最有名的就是 LeetCode 556“下一个更大元素 III”——给你一个正整数 n让你调换它的各位数字得到大于 n 的最小整数不存在则返回 -1。这道题本质就是把正整数拆成数字数组先做一遍“下一个排列”然后检查结果是否还在 int 范围内。我当年刷到 556 时第一反应是“这题跟 31 有啥关系”把 31 的代码搬过来之后发现几乎不用改只需要处理两个额外事项一是把输入整数先转成数组二是做完 nextPermutation 之后判断一下结果的首位是不是 0如果原数位数相同首位不能是 0。这个迁移过程比你自己从零想一个解法快得多也稳得多。再往远处看“下一个排列”的思路在全排列生成算法字典序法里也是核心。LeetCode 46“全排列”如果你用标准库的next_permutation来做背后的实现就是这道题的逻辑。很多 C 选手天天用std::next_permutation却不知道它内部就是这段“从右往左找升序对、交换、反转”的流程。弄懂了 LeetCode 31你就等于把标准库一个高频功能的内幕彻底看穿了。排序算法里也会用到类似“从右往左扫描找逆序对”的结构。比如冒泡排序每轮会把最大值“冒”到最右边这个从右往左或者从左往右扫描的过程和你找 i 的过程在思路上有相通之处——都是在局部序列里寻找顺序关系的破坏点。虽然它们解决的问题不同但“扫描方向 相邻比较”这个组合是很多数组操作题的共性骨架。贪心算法就更不用说了。找 j 的过程就是一个典型的贪心选择在候选集里挑一个最优的元素。很多人觉得贪心抽象但放到这个场景里目标明确最小的更大数约束清晰右侧降序贪心策略就变得非常自然。所以我一直觉得LeetCode 31 是一道“性价比”极高的题。它代码短、边界多、思想深、延伸广。你花一个下午把它彻底吃透后面遇到 556、46、47甚至某些排列相关的回溯题都能省不少力气。6. 我踩过的坑和总结出的判断口诀最后说几个我自己刷这道题时踩过、也见证过别人踩的坑以及一个可以让你少走弯路的判断口诀。第一个坑是“从右往左找升序对”这个方向搞反。新手第一次写特别容易写成从左往右找第一个降序对。方向一反整个算法全乱。你只要记住一句话右边的数字已经处于“最大形态”降序时它是不能内部变大的一定要从更左边借一个数字来“抬升”。所以扫描必须从右往左找到的第一个升序对就是最后一个还能变大的位置。第二个坑是第二步“交换之后直接 reverse 右侧”时有人会想右侧不一定是升序啊是不是得先 sort我当时也犹豫过后来想明白了因为你在右侧找 j 时取的是“最小的比 a[i] 大的元素”并且是从右往左扫的所以交换之后右侧依旧保持降序不变。降序直接反转必得升序完全不需要排序。这个“交换不破坏右侧降序”的性质是这道题最精妙的地方。第三个坑是重复元素。前面提到的和缺一个等号结果就错。刷题时如果测试用例带着重复元素特别容易翻车。建议你写完代码之后专门把[1, 5, 1]、[1, 4, 2, 2]、[2, 3, 1, 3, 3]这种带重复数字的用例手跑一遍比单纯背代码有效得多。第四个坑是“已经最大排列”的情况。比如[3, 2, 1]循环退出来 i -1这时候直接整体反转。很多人会忘记处理 i -1 的情况导致 reverse 起点不对或者越界。一个很简单的自查方法代码里reverse(nums.begin() i 1, nums.end())这个写法在 i -1 时正好是reverse(nums.begin(), nums.end())分毫不差。所以这个写法本身就是在帮你兜底。如果你想要一个快速记忆的口诀我自己的是一找升序对二挑最小大三换位四翻转。十二个字够你面试时在脑海里过一遍流程了。这道题刷完之后建议顺手做两道练习题巩固LeetCode 556下一个更大元素 III和 LeetCode 46全排列如果用了标准库试着关了它手写一遍。把排列生成与字典序这两个概念串起来你对“下一个排列”的理解就不会只是停留在背代码的层面而是真正内化成了算法直觉。以后不管是笔试、面试还是实际工程里碰到“按字典序生成所有方案”之类的需求这道题的思路都能直接迁移过去属于典型的“花一小时学会、吃十年老本”的题目。