1. 这题到底在问什么一个连官方示例都会误会的下一个排列先别急着看题解我见过太多人卡在第31题上不是因为算法难而是因为压根没理解清楚题目说的下一个排列是个什么东西。我第一次做这道题的时候也是这样看到示例[1,2,3] - [1,3,2]心里想这不是很简单吗最后两位换一下不就行了结果提交一跑[1,2,3,4]应该输出[1,2,4,3]也对[1,3,2,4]应该输出什么我按最后两位交换的思路算出来是[1,3,4,2]实际答案却是[1,3,4,2]……好像碰巧对了。但一旦遇到[1,5,1]这种用例马上就露馅。1.1 从字典序说起为什么排列是有顺序的题目说的下一个排列完整说法应该是字典序的下一个排列。字典序是个什么概念你就想象在查英文字典先比较第一个字母abc排在abd前面如果第一个字母相同比较第二个字母。数字排列也是同理——把整个排列当成一个多位数去比大小[1,2,3]看成123[1,3,2]看成132那自然123 132 213 231 312 321。所以下一个排列的意思就是在所有由同一组数字组成的排列中按从小到大排序后紧跟当前排列后面的那一个。注意这句话里有三个关键限定同一组数字、全排列、紧挨着。很多人做题时把这三点抛到脑后拿交换某两个位置的局部思路去硬套做出来的结果经常是比原排列大但跳过了中间好几个排列或者更离谱的比原排列还小。1.2 官方示例拆解[1,2,3] → [1,3,2]是怎么来的[1,2,3]这个排列全排列按字典序排出来是[1,2,3] - 123 [1,3,2] - 132 [2,1,3] - 213 [2,3,1] - 231 [3,1,2] - 312 [3,2,1] - 321[1,2,3]是第一项紧跟其后的就是[1,3,2]。所以示例里的变换不是随便把3和2对调而是正好对调后得到的132恰好就是字典序里紧随其后的那个排列。那为什么[2,3,1]的下一个不是[3,1,2]把最后两位交换而是[3,1,2]等等这题换位就碰巧对了不对[2,3,1]的全排列序列中231后面确实是312但交换方式不是最后两位换而是[2,3,1] - 交换2和3 - [3,2,1]再反转后缀得到[3,1,2]。可见只是局部交换两个位置这种思路碰巧在某些用例上撞对了答案本质上是没有理解规律的。1.3 两个特殊案例为什么[3,2,1]转回[1,2,3]而不是没有下一个再看一个关键问题[3,2,1]是全排列字典序里的最后一项它没有下一个了。但题目要求输出[1,2,3]也就是绕回字典序最小的排列。这就像钟表的时针走完12点之后归1是一个循环关系。题目这句话描述为如果不存在下一个更大的排列则将数字重新排列成最小的排列即升序排列。这个设计在工程上是有意义的C STL的next_permutation也是这么干的配合do...while循环就可以无重复地遍历完所有排列。也就是说算法在最后一项时的行为不是返回失败而是重置到初始状态这样调用方只要一直调用就能穷举所有排列而不需要自己关心边界。后面我讲到代码实现时你会发现降序数组直接反转成升序这一步正好利用了这个循环语义代码简洁自然。2. 暴力法的真实代价从全排列生成到next_permutation的演化史理解了题意之后第一反应通常是我把这个数组的所有全排列都列出来排序然后找到当前排列的下一个不就行了这个思路没错错在代价上。n个不同元素的全排列数量是n!。当n12时12! 479001600近5亿种排列哪怕每种排列只花1微秒生成也要8分钟。而力扣的测试用例数组长度上限通常是100或更大这个数据规模下暴力法完全是天文数字。2.1 纯暴力生成全排列再找下一个的时间成本先别急着否定暴力法把它作为思考起点是好的。假设数组长度为n暴力方案大概是先递归生成全部n!个排列存下来排序再线性查找当前排列的位置输出它的下一个。三个步骤的复杂度分别是生成O(n!)、排序O(n! log(n!))、查找O(n! * n)。在n10的时候已经是3628800种排列排序加上字符串比较的开销本地跑起来会明显卡顿。更不用说力扣有执行时间限制这种解法连n100的大门都摸不到。2.2 计算机领域早有标准答案C STL的next_permutation那有没有更聪明的办法实际上这个问题在计算机领域早就有标准答案了。C STL里的next_permutation函数就是干这个的很多用C刷题的人甚至直接调这个库函数就把题过了。但面试官问这道题的目的恰恰是让你把STL里那个函数的内部原理手写出来。我在面试中问过不少候选人能直接说出next_permutation名字的不少但真能讲清楚它内部找下降点、交换、反转三步的十个里也就一两个。2.3 从STL实现反推算法思路STL的实现思路其实很朴素核心就是在问一个问题要得到比当前排列大的下一个排列我们应该把哪一位变大同时让增大的幅度尽量小玩过数字排列的人会有一种直觉从右往左看如果某一位后面还有比它大的数字那么把它换大后面的数字再重排成最小就能得到一个刚好更大的排列。这个直觉就是标准解法的前身。接下来要做的就是把哪一位换谁后面怎么重排这三件事精确化。3. 核心规律从右往左找下降点的标准三步法直接给结论标准解法就三步顺序是从右往左扫描共O(n)时间O(1)额外空间。3.1 算法流程一句话总结用一句话概括找到从右往左第一个升序被破坏的位置把它和右边刚好比它大的最小元素交换再把右边那一段反转成升序。很多人第一次看这句话很晕拆开看就不晕了。为了统一术语我把数组下标定为i从n-2往前找找到第一个满足nums[i] nums[i1]的位置这个位置叫做下降点也叫拐点。然后从数组尾部往前找第一个大于nums[i]的元素记为j交换i和j最后把i1到数组末尾这段反转。3.2 第一步找第一个降序对从右向左的原理为什么是从右往左找第一个nums[i] nums[i1]因为排列的字典序优先比较高位。高位一旦变大无论后面多小整个排列一定变大高位不变才轮到下一位去变化。从右往左找找到的第一个升序被破坏的地方本质上是从右往左看第一次出现后面的数字比前面大的位置。换句话说i右侧的所有元素是单调递减的因为从右往左扫过来一路都是nums[k] nums[k1]才能继续往前。这意味着以i为分界点右侧已经处于当前后缀能组成的最大排列状态。想要整体变大必须动i本身把i这个位置换成右边更大的某个数。这就像把一个数从123654变到124356654这后缀已经是最大了不动3光调整654只会越来越小所以必须把3变大。3.3 第二步找右侧刚好大于该点的最小元素为什么不是随便换一个找到下降点i之后右侧是降序排列的。我们想找一个元素和nums[i]交换让整体排列变大。问题来了换谁答案是从右往左找第一个大于nums[i]的元素。为什么从右往左因为右侧是降序从右往左扫第一个大于nums[i]的元素就是所有大于nums[i]的元素里最小的那个。这保证了交换之后新排列比原排列大但是大得最少。举个例子nums [1, 5, 8, 4, 7, 6, 5, 3, 1]。从右往左找到第一个升序破坏点是4下标3右侧是[7,6,5,3,1]降序。从右往左找第一个大于4的数扫到5时发现5 4停在5下标6。为什么选5而不是7或6因为7和6虽然也大于4但交换5得到的整体数字比交换6、7得到的数字更小更贴近下一个的要求。这就像在说高位从4变到5、6、7都能让数变大但我们要的是紧挨着的下一个当然是变化越小越好。3.4 第三步右侧逆转为升序恢复字典序最小交换nums[i]和nums[j]之后i位置已经变成了一个更大的数这保证了新排列比原排列大。但此时i右侧仍然是降序。降序是什么概念是这组数字能组成的最大排列。放在更高的i位之后如果右侧保持降序整体数字反而是i位固定时能取到的最大值不是我们想要的——我们已经把高位变大了一点低位应该尽量小才能保证整体是紧挨着的下一个排列。所以第三步就是把i1到末尾这段反转让降序变成升序。升序是这组数字能组成的最小排列。高位刚变大一点低位取最小整体正好就是字典序里紧跟后面的那个。还是用刚才的例子[1,5,8,4,7,6,5,3,1]交换4和5之后得到[1,5,8,5,7,6,4,3,1]把i14到末尾的[7,6,4,3,1]反转成[1,3,4,6,7]最终结果是[1,5,8,5,1,3,4,6,7]。对照一下这个结果确实比原排列大而且中间没有隔其他排列。3.5 完整代码实现Python 注释理论讲了一堆代码其实很短。我先把Python写法贴出来def nextPermutation(nums): n len(nums) # 第一步从右往左找第一个升序被破坏的位置 i n - 2 while i 0 and nums[i] nums[i 1]: i - 1 if i 0: # 第二步从右往左找第一个大于 nums[i] 的元素 j n - 1 while j 0 and nums[j] nums[i]: j - 1 # 交换 nums[i], nums[j] nums[j], nums[i] # 第三步反转 i1 之后的部分无论是否找到下降点都要执行 left, right i 1, n - 1 while left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1注意第三步不管i是否为-1都会执行。如果整个数组是降序比如[3,2,1]第一步扫完i会变成-1此时不需要交换直接反转整个数组得到[1,2,3]正好符合题目对不存在下一个排列时重排为升序的要求。这个设计非常优雅等于把边界情况直接合并进了统一流程。4. 最容易翻车的三处边界降序数组、重复元素、原地修改算法主体讲明白了但真正动手写的时候我见过不下十个人在边界条件上栽跟头。这里把最容易翻车的三个点单独拎出来说。4.1 降序数组循环到头部才是下一个如果整个数组严格降序说明当前已经是字典序中最大的排列。按照题目要求直接反转整个数组变成升序。有些人的代码会在i 0时提前return然后单独写一段翻转逻辑这其实没必要因为只要把反转范围设为整个数组统一代码路径反而更不容易漏分支。我在写第一版的时候就在这个分支里反复判断结果逻辑绕来绕去最后还是统一成不管找没找到下降点都反转i1到末尾代码瞬间清爽。还有一个很容易被忽略的点反转和交换要区分清楚不要因为整个数组降序就把交换也跳过——跳过交换是对的因为根本没有可交换的元素但千万不要把反转也跳过了。4.2 重复元素相等不要交换的细节力扣这题的输入可能包含重复数字比如[1,5,1]或[2,2,7,5,4,3,2,2]。很多人在两个while循环里用错比较符号导致死循环或者换错。关键点有两个。第一个第一步找下降点的while条件是nums[i] nums[i 1]注意是大于等于不是大于。如果用那遇到[1,1,5]这种连续相等的开头会把第一个1当成下降点导致答案错误。从右往左扫相等元素不构成严格升序所以当nums[i] nums[i1]时要继续往前找。第二个第二步找交换元素的while条件是nums[j] nums[i]这里要用小于等于跳过相等元素确保找到的是严格大于nums[i]的元素。如果用了遇到[1,3,3]这种情况i指向的是下标1的3从右往左找第一个大于3的元素时会停在下标1本身因为nums[1] nums[i]不够大但判断会跳过它直到找到比3大的如果没有比3大的会扫到i位置但那个位置3 3仍然成立继续往前扫最终导致找不到。这里符号的选择直接决定代码的正确性建议背下来找下降点用找交换点用。用[1,3,3]完整走一遍帮助理解重复元素从右往左比较nums[1]3和nums[2]3相等不满足nums[1] nums[2]继续往前比较nums[0]1和nums[1]3找到下降点i0。从右往左找第一个大于1的元素nums[2]3 1所以j2交换得到[3,3,1]反转下标1之后的部分[3,1,3]。验证一下字典序[1,3,3] - [3,1,3] - [3,3,1]正确。4.3 原地修改的限制与空间复杂度题目明确要求必须原地修改只允许使用额外常数空间。很多人用Python写nums sorted(nums[i1:])这种切片赋值乍一看逻辑没错但其实切片会生成新列表严格来说不符合原地要求而且如果写成nums[i1:] sorted(nums[i1:])虽然结果对但空间复杂度变成了O(n)面试里容易被追问。所以标准做法是用双指针反转也就是上面代码里的left, right循环空间O(1)干净利落。C选手直接reverse(nums.begin() i 1, nums.end())更省事。5. 复杂度分析与正确性证明为什么贪心策略必然得到正确解这一节写给喜欢刨根问底的读者。算法虽然短但如果你只是背下三步流程面试官一追问为什么这样一定对很容易卡壳。我们要把正确性证明和复杂度讲清楚。5.1 时间复杂度的直观分析三步操作里第一步从右往左扫描最坏情况扫描n个元素第二步从右往左扫描最坏情况也是n个元素第三步反转同样是O(n)。所以整体时间复杂度是O(n)空间复杂度O(1)。这里的n是数组长度。这个复杂度已经是最优了——因为你至少要读一遍数组才能确定下降点在哪反转操作绕不开移动后半段元素的成本所以不可能比O(n)更快。5.2 证明为什么交换最右侧的升序破坏点能得到字典序最近的下一个严谨的证明可以分成三个引理来理解。引理一从右往左第一个nums[i] nums[i1]的位置是唯一可能需要高位变动的位置。因为i右侧是降序这个后缀已经是它能组成的最大排列光调整后缀内部元素只会得到比当前后缀更小的排列整个数组无论如何不会变大。要想整体变大只能让i位置本身变大。引理二交换nums[i]与右侧第一个大于它的元素能使整体变大的幅度最小。右侧是降序第一个大于nums[i]的元素就是右侧所有大于它的元素中的最小值。如果换一个更大的元素比如第二大的那i位提升得更多得到的排列必然更大也就跳过了若干字典序介于中间的排列。引理三交换之后把后缀反转成升序能得到i位固定时的最小后缀。因为交换前右侧是降序交换后把第i位换成稍大的数字后右侧仍然保持降序反转后变成升序升序就是同组数字能排成的最小序列。高位刚变大为某个值后缀取最小整体就是大于原排列的所有排列中最小的那一个也就是字典序的下一个。三个引理合起来就证明了标准三步法的正确性。这个证明思路在面试里很加分我建议你不用背而是用自己的话把为什么选最右侧的拐点和为什么选刚好更大的元素讲清楚。5.3 用一个具体例子完整走一遍再来一个完整走一遍这次用[2,3,1,3,3]。第一步从右往左扫描比较nums[3]3和nums[4]3相等不满足比较nums[2]1和nums[3]3满足1 3所以i2。第二步从右往左找第一个大于1的元素nums[4]3nums[3]3nums[2]1找到j4当然也可以选j3但按代码逻辑从右往左第一个是下标4。交换nums[2]和nums[4]得到[2,3,3,3,1]。第三步反转下标3到4的部分[3,1]得到[2,3,3,1,3]。如果你把所有含两个重复3的排列按字典序列出来[2,3,1,3,3] - 23133 [2,3,3,1,3] - 23313 [2,3,3,3,1] - 23331可以看到[2,3,1,3,3]的下一个确实是[2,3,3,1,3]算法输出的结果和字典序完全吻合。6. 从第31题延伸出去的经典题全排列、下一个更大元素、排列的排名刷题千万别只刷一道就完事。第31题作为排列类题目的地基后续连着好几道题都是它的变体或者姊妹题。把这条线串起来你的刷题效率会高很多。6.1 第46/47题全排列与第31题的关系第46题全排列无重复数字的经典解法是回溯但还有一种冷门做法nums初始为[1,2,3,...,n]反复调用next permutation这一步每调用一次就产生一个排列直到回到初始状态。这种方法的时间复杂度是O(n * n!)其中n是每次调用next permutation的开销n!是排列总数。它比回溯慢但在某些需要按字典序逐个生成排列的场景里非常自然。第47题是全排列II输入可能有重复数字这时候用next permutation方法反而比回溯剪枝更不容易出错——只要每次从当前排列出发生成下一个天然就不会产生重复排列。我在做第47题时试过两种方法最后发现用第31题的算法配合do-while风格的循环代码最简洁。6.2 第496/503题下一个更大元素同是下一个但思路完全不同下一个排列和下一个更大元素虽然名字里都有下一个但思路完全不同。下一个更大元素是找每个元素右边第一个比它大的数用单调栈解决下一个排列是调整整个数组的字典序后继。很多人把这两类题混为一谈一看到下一个就想到单调栈结果第31题怎么都想不出来。建议刷到第496题时专门对比一下这两类题的差异给自己做一个表格式的总结印象会非常深刻。6.3 变体求上一个排列、字符串版本、k-th排列第31题还有几个实用的变体。变体一是求上一个排列。两种思路一是把数组反转之后做一次next permutation再反转回来二是把标准三步法反过来——从右往左找第一个nums[i] nums[i1]的位置再找右侧刚好小于nums[i]的最大元素交换最后把后缀反转成降序。变体二是把数组换成字符串做法完全一样只要把比较数字改成比较字符。变体三是第60题排列序列给定n和k返回第k个排列那题用阶乘数系也叫Lehmer code可以直接算出来不需要循环调用k次next permutation避免超时。6.4 一题多解对比表题目/变体核心方法时间复杂度空间复杂度和第31题的关系第31题 下一个排列找拐点交换反转O(n)O(1)母题第46题 全排列回溯 或 反复调用nextO(n!)O(n)next是生成方法之一第47题 全排列II反复调用nextO(n * n!)O(1)不算输出天然去重第60题 排列序列阶乘数系O(n^2) 或 O(n)O(n)正向计算的进阶版求上一个排列对称三步法O(n)O(1)思路镜像这张表我每次讲第31题都会画出来因为它说明了一道基础题往深处挖可以挖出一整棵知识树。7. 实测经验与刷题策略这道题放在什么阶段刷最合适7.1 我踩过的坑与Bug复盘第一次写这道题的时候我犯了一个非常蠢的错误把第一步的while条件写成了nums[i] nums[i1]然后整个算法在[1,2,3]这个用例上直接输出[1,2,3]——因为从右往左第一步就发现3 2i直接变成1但其实下降点应该是nums[1]2 nums[2]3一上来方向就反了。后来在纸上把数组从右往左标号走了一遍才意识到找下降点是在找右边的数比左边的数大的地方而不是左边的数比右边大。这个错误很有代表性它提醒我任何时候写双指针扫描的边界条件最好先用一个5元素左右的数组在纸上模拟一遍不要直接提交。第二个坑是关于j的查找范围。我一开始写的第二层循环是while nums[j] nums[i]: j - 1没有处理等于的情况结果在[1,5,1]上报错从右往左找到拐点i1nums[1]5 nums[2]1等等这个数组[1,5,1]是降序1 5拐点其实是下标0查找j时nums[2]1不大于nums[0]1所以继续往前nums[1]5大于1j1交换后得到[5,1,1]反转下标1到2的部分得到[5,1,1]……但正确答案应该是[5,1,1]吗这里值得完整验证一下[1,5,1]的全排列字典序为[1,1,5] - [1,5,1] - [5,1,1]所以[1,5,1]的下一个确实是[5,1,1]。但如果把写成在某些用例下会找到不合适的交换位置。总之比较符号要严格用跳过相等元素。7.2 面试考法手写 vs 调库 追问这道题在面试中出现频率不低常见的考法是让你手写next_permutation然后追问三连时间复杂度是多少能不能优化如果输入有重复元素怎么办有经验的候选人会先问清楚重复元素是否算作不同排列然后按标准三步法写。有些候选人张口就说直接调用next_permutation这种回答在工程场景下没错但面试题考察的恰恰是库函数背后的原理一旦被追问就露馅。我建议就算你知道STL有现成函数也要说清楚如果允许调库我会用std::next_permutation但既然考察算法我手写一遍。既表现了对库的了解又展示了算法功底。7.3 配套练习清单最后给一份配套练习路径每道题之间最好隔一两天再刷给自己留出思考的时间第46题 全排列用回溯写出全排列再用第31题的方法生成全排列对比两种写法第47题 全排列II体会重复元素下next permutation自动去重的优势第60题 排列序列正向推导第k个排列不必循环调用next第556题 下一个更大元素III实际上就是给定数字n返回下一个字典序更大的排列对应的整数是第31题的整数版本还要处理溢出问题第1053题 交换一次的先前排列反向思维找前一个排列的变体这几道题刷完你基本就把排列字典序这一整个小专题拿下了。我自己刷题的习惯是每道题写完之后再在旁边记录一句话总结和一个变形思路比如这题我写的是高位变大后缀取最小找拐点注意等于号。过三个月再回来看这句话能瞬间回忆起整个算法比重复刷三遍都管用。
