最近在刷力扣hot100的时候我又一次碰到了这个题。说实话“下一个排列”这道题我第一次做的时候完全是懵的看懂题解之后觉得“就这”,但真正到自己手写又总是会在边界条件上翻车。后来刷的次数多了才发现这道题几乎是所有全排列类问题的地基面试里也经常作为热身题出现而且它背后那套“从右往左找规律”的思维方式在你遇到其他数组类题目时也会反复用到。所以我想把这道题的完整推导过程、代码实现、边界陷阱和几个常见变体一次性写清楚希望能帮你彻底吃透它而不是背住解法。题目本身不复杂给定一个整数数组要求找出这个数组所有元素排列成的数字序列中字典序紧接着当前排列的那个排列并且必须原地修改只允许使用常数级别的额外空间。如果当前排列已经是字典序最大的那个就把它重新排列成字典序最小的排列。举个直观的例子[1,2,3]的下一个排列是[1,3,2]而[3,2,1]的下一个排列是[1,2,3]。1. 题目背后的真实考点字典序和“下一个”的数学含义很多人拿到这个题的第一反应是把所有排列全列出来排序然后找到当前排列的下一个。对于[1,2,3]这种小数组这当然可行三个元素全排列也就六种。但力扣的数组长度可以到100100的全排列数量是天文数字别说枚举连存储都放不下。所以这个题真正的考点不是“如何枚举排列”而是“如何利用字典序的规律只通过局部调整就得到答案”。1.1 先搞懂什么是字典序排列字典序在英文里叫lexicographical order它本质上就是我们查英文字典时用的规则先比较第一个字符如果相同再比较第二个依此类推。放到数字排列上就是把数组的每个元素当作一个“字符”整体当作一个字符串去比较大小。比如[1,2,3]和[1,3,2]这两个排列第一位都是1第二位2小于3所以[1,2,3]在字典序上排在[1,3,2]前面。这里有一个特别容易忽略的点数组元素不一定是连续的整数也可能有重复比如[2,1,2]。重复元素会让全排列的个数变少但字典序比较规则不变。后面讲代码实现的时候我会专门提到重复元素下等号处理的细节。1.2 如果用暴力法会发生什么假设数组长度为n全排列的数量是n!。n10的时候就是3628800种勉强还能算n12的时候接近5亿种暴力已经不可能的。即便你能生成全排列要找到当前排列的下一个还得做一次线性查找时间复杂度和空间复杂度都无法接受。所以这个题一开始就不是让你去枚举的它考察的是你有没有能力从一个具体的排列出发推断出“排在它后面的那个排列应该长什么样”。我自己一开始刷这个题的时候也走过暴力枚举的弯路。后来反复看官方题解才慢慢意识到所谓“下一个排列”本质上是“在不改变高位元素的情况下尽量让低位元素变得更大一点”。这个视角非常关键因为它直接引导出标准解法的那三步操作。2. 标准解法推导从右往左找规律的三步操作标准的解法其实非常简洁核心思想可以概括成三句话从右往左找到第一个相邻的升序对在右侧找到比当前位置大的最小元素交换后把右侧反转成升序。这三句话背起来容易但为什么是这样每一步解决了什么问题很多人其实没有真正想明白导致换个题目就不会了。2.1 第一步为什么必须从右往左找第一个降序点我们先从一个具体的排列说起。假设当前排列是[1,3,5,4,2]它的下一个排列是什么很多人第一眼会尝试动第一位把1换成更大的数但那样得到的结果会非常大显然不是“紧接着”的那个。正确的直觉应该是尽量不要动高位只在最靠右的、允许变大的位置上操作。那怎么找到“最靠右的允许变大的位置”我们从右往左扫描比较相邻的两个元素nums[i]和nums[i1]。如果nums[i] nums[i1]说明从i位置到末尾的子序列是降序的或者完全相等的这个子序列已经是它所有排列中字典序最大的形态了没有“下一个排列”可言所以继续往左走。一旦遇到nums[i] nums[i1]这个i就是我们要找的位置。为什么因为i右侧的整个后缀是降序的或者等值的它已经是最大形态不可能通过调整后缀内部得到更大的排列。想要得到下一个排列必须动第i位本身把它换成一个更大的数然后让i右侧重新调整为最小的形态。这个i就是整个排列中“从右往左看第一个破坏了降序规律”的位置也是唯一还有潜力增大的位置。2.2 第二步交换的目标为什么是“右侧比它大的最小元素”找到位置i之后我们要把nums[i]换成一个更大的数。但换谁答案不是右侧最大的那个而是“右侧比nums[i]大的最小元素”。因为我们要找的是“下一个”排列也就是说变化的幅度要尽可能小。如果直接换成右侧最大的数得到的排列会跳得太远中间会漏掉很多合法的排列。由于i右侧是降序的所以从右往左扫过去第一个大于nums[i]的元素就一定是最小的那个大于nums[i]的元素。这一步你不需要额外排序也不需要线性查找多次从右往左一次遍历就能锁定。交换之后nums[i]位置变成了一个“恰到好处”的更大值剩下的问题就是如何让i右侧变成“最小的排列”。2.3 第三步交换后右侧反转的真正原因交换之后i右侧依然保持着降序在原来的降序序列中把某个元素换成了更小的值整体依然是降序而降序是整个后缀字典序最大的形态。为了让整个排列成为“紧接着的”那一个我们必须把这个后缀变成字典序最小的形态也就是升序。对于降序序列翻转一遍就是升序时间复杂度O(n)不需要调用排序函数更不需要额外空间。到这里三步操作就齐了找i、找j、交换、反转。用例子跑一遍[1,3,5,4,2]从右往左找到nums[i]3因为35然后在右侧找比3大的最小元素从右往左第一个大于3的是4交换得到[1,4,5,3,2]最后把i1到末尾的反转得到[1,4,2,3,5]。你可以手动枚举一下[1,3,5,4,2]的所有后续排列这个结果确实是正确的。3. 两种主流语言的落地实现与细节陷阱原理清楚了代码写起来就很快。我用C和Python各写一版然后重点讲一下两个最容易出错的等号细节和边界条件。3.1 C实现class Solution { public: void nextPermutation(vectorint nums) { int n nums.size(); int i n - 2; // 从右往左找第一个 nums[i] nums[i1] while (i 0 nums[i] nums[i 1]) { i--; } if (i 0) { int j n - 1; // 从右往左找第一个大于 nums[i] 的元素 while (j 0 nums[j] nums[i]) { j--; } swap(nums[i], nums[j]); } // 反转 i1 到末尾 reverse(nums.begin() i 1, nums.end()); } };这段代码有一处非常关键如果整个数组已经是降序那么第一个while循环会把i扫到-1此时不需要交换直接反转整个数组。这个逻辑恰好对应了题目说的“如果已经是最大排列就返回最小排列”。很多人在写的时候会忘记判断i 0就去做交换结果越界这个错误非常隐蔽。3.2 Python实现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] nums[i 1:] reversed(nums[i 1:])Python的切片反转非常方便但要注意nums[i 1:] reversed(nums[i 1:])这行它会原地修改列表。如果你写的是nums[i 1:] nums[i 1:][::-1]也可以效果一样。两种写法都是O(n)时间空间上因为切片会生成一个新列表严格来说不是O(1)但在实际刷题中通常不会被卡。3.3 两个等号细节必须抠死第一个等号细节在第一个while循环里nums[i] nums[i 1]这个是有讲究的。如果数组里有重复元素比如[2,1,1]从右往左扫描时1不小于1所以i会继续往左走到2找到nums[0]2 nums[1]1吗不对2不小于1所以i会变成-1说明[2,1,1]已经是最大排列直接反转成[1,1,2]。如果这里写成了nums[i] nums[i 1]那么当遇到相等的相邻元素时会被误判成升序点导致后面找交换位置时出现逻辑错误。第二个等号细节在第二个while循环里nums[j] nums[i]同样是严格小于才继续往左走。如果写成nums[j] nums[i]当右侧有和nums[i]相等的元素时j会停在一个等于它的位置上交换后不会有任何变化排列没变程序却认为已经完成结果就是死循环或跳不出正确结果。这两个等号你在纸面上推演时可能感觉不到问题但一跑测试用例就会暴露。4. 进阶扩展从“下一个排列”到全排列问题族说这个题是“排列类问题地基”一点都不夸张。力扣上的全排列、排列序列、上一个排列等题目本质上都离不开这套“找降序点、交换、反转”的思维。我在这里把几个高频变体和它们的思考方向一起列出来。4.1 上一个排列镜像对称的解法求上一个排列和求下一个排列完全对称。求下一个是找“从右往左第一个升序点”求上一个就是找“从右往左第一个降序点”下一个要交换“右侧比它大的最小元素”上一个就交换“右侧比它小的最大元素”交换后下一个要把右侧反转成升序上一个要把右侧反转成降序。如果你能独立把“上一个排列”写出来说明你对这套规律是真的理解而不是背答案。我建议你刷题的时候把两道题放在同一天做。先自己写“下一个排列”然后不看题解尝试写“上一个排列”。你会发现自己对“右侧后缀已经是某种顺序”这件事的感知会强很多遇到其他数组题时也会更敏感。4.2 求第k个排列阶乘数系统力扣第60题“排列序列”是另一个高频题它问的是给定n和k返回第k个排列。这道题的标准解法是用阶乘来定位每一位。比如n4第一个位置每进一位会跳过3! 6个排列所以用(k-1)/6就能确定第一个数字是谁。定位完第一位后把剩余数字重新编号继续用(k-1)%6去定位第二位。这个过程和“下一个排列”看起来完全不同但核心思想都是“排列的顺序是由每一位的相对大小决定的”理解了字典序的几何意义之后这道题其实也不难。顺带提一句C标准库里的next_permutation函数内部实现和这道题的解法基本一致但它是用迭代器实现的并且当排列已经是最大时返回false同时会把数组重置为最小排列。如果你对库函数好奇可以自己写一个类似的模板函数用来加深理解。4.3 带重复元素的全排列生成如果你用回溯法生成全排列[1,1,2]这类带重复输入的题目去重逻辑通常需要“先排序再在递归中跳过和前一个相同的元素”。那么问题来了排序之后的第一个排列就是最小排列利用“下一个排列”不断迭代也能不重不漏地生成所有全排列而且不需要额外的used数组去重天然就能避开重复排列。这个思路在很多竞赛代码里经常出现因为next_permutation本身处理重复元素时得到的结果序列是严格不重复的。5. 实战中的踩坑记录和刷题建议这部分我想聊聊自己在实际写这个题和讲这个题时经常遇到的坑以及一些能帮助你更快落地的经验。这些内容你在官方题解里看不到但面试和笔试里很实用。5.1 最容易翻车的三个测试用例第一个是单元素数组[1]。很多人会下意识认为至少需要两个元素才能找升序对结果while循环的条件写成了i 0 nums[i] nums[i1]当i初始为-1时访问nums[-1]直接越界。正确的做法是让i从n-2开始n1时i-1while条件直接不成立自然进入反转环节反转长度为0原数组不变。第二个是最大排列[3,2,1]。这个用例验证的是“整体降序时直接反转整个数组”这一分支。如果你没有对i0做判断就执行swap会出现下标为-1的访问错误如果你忘了反转返回的还是[3,2,1]结果错误。第三个是重复元素[1,5,1]。从右往左扫描51所以i停在1的位置下标0因为15是升序然后在右侧找比1大的最小元素从右往左找到5交换得到[5,1,1]反转右侧得到[5,1,1]。等等这里我故意写了一个容易算错的例子。正确的做法[1,5,1]中nums[0]1, nums[1]5是升序所以i0右侧比1大的最小元素是5吗不是右侧是[5,1]比1大的只有5交换得到[5,1,1]反转[1,1]还是[1,1]结果[5,1,1]。这个结果是正确的。那如果输入是[1,1,5]呢从右往左找到i1因为nums[1]1 nums[2]5交换1和5得到[1,5,1]反转[1]结果[1,5,1]。也是正确的。5.2 面试中如何有条理地讲清思路面试官让你做这个题通常不是为了看你背代码而是想听你的推导过程。我的建议是先举一个小例子说明什么是字典序然后从暴力法出发说明枚举n!不可行接着用“尽量不动高位、只动最靠右的可变大位置”这个直觉引出从右往左扫描每做一步都用刚才的例子现场演示变化过程最后补上时间复杂度和空间复杂度的分析。如果面试官追问“为什么右侧后缀反转就是最小排列”你要能答出因为右侧后缀在找到i时是降序的降序的反转恰好是升序而升序是所有排列中字典序最小的形态。这个回答需要你对“降序最大、升序最小”的结论有直觉上的认同而不是仅仅记住这句话。5.3 这个题还能怎么考在原题基础上面试官经常会出一个变形“给定一个数字字符串求用这些数字能组成的大于当前数字的最小整数。”这就是“下一个排列”的字符串版本只是把整数数组换成了字符数组比较大小换成了字符比较。很多人在换了个容器之后就反应不过来其实核心代码几乎一模一样。还有一种考法是“给你一个排列求它在所有排列中的序号。”这个需要用到康托展开思路是统计每一位后面有几个比它小的数字然后乘以后面位数的阶乘。理解了“下一个排列”的字典序含义后康托展开的公式就不难理解了。结束语我对这道题最大的体会是背解法永远不如推解法。当你真正理解了“从右往左找降序点、右侧找最小更大值、交换后反转”这套逻辑的来源之后你会发现它本质上是一种“局部贪心”的策略——在保证高位不变的前提下让变化发生在尽可能靠右的位置同时让变化幅度尽可能小。这个思维模型在很多数组问题里都能复用比如找下一个更大元素、接雨水、单调栈相关的题目背后都有类似的“从右往左观察规律”的思路。如果你现在正在刷力扣hot100建议把这道题和全排列、排列序列、上一个排列放在一起集中突破。先用三五分钟自己推导再看题解对照最后合上代码手写一遍直到能无bug一次通过。这样练下来这个题才算真正长在你身上了。