LeetCode热题100“下一个排列”全解析：字典序、双指针与Java原地实现

刷LeetCode热题100的Java选手大概率都绕不过“下一个排列”这道题。它是力扣第31题也是《热题100》里很特殊的一道题面极短、描述朴素却同时考察了字典序理解、数组原地操作和双指针的运用。很多人在面试时碰到它第一反应是“这不就是找更大的数吗”结果一写就错也有人背下了标准解法代码能过但被追问“为什么最后一步是反转而不是排序”时当场卡壳。这篇博文就把这道题从题目语义、算法推导到Java实现、面试追问一次性讲透尤其是那些常规题解里不会写清楚的细节和坑希望你看完之后能真正“拿捏”它而不是只会默写。1. 题目到底在问什么先别急着写代码1.1 原题复述与示例解读题目原文其实很短给定一个整数数组把它重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列则重新排列成字典序最小的排列。要求原地修改只允许使用常数级别的额外空间。先记住三个关键约束原地修改、O(1)额外内存、处理“不存在下一项”的降序情况。很多人忽略了“原地修改”第一反应是“把数字转成字符串再转成下一个排列”这种思路在工程上可行但在本题直接判负。再看三个示例输入输出说明[1,2,3][1,3,2]存在更大的排列取最小的那个[3,2,1][1,2,3]已经是最大排列回到最小排列[1,1,5][1,5,1]重复元素也要按字典序正常处理第三个示例特别容易错。有人觉得[1,1,5]的下一个应该是[5,1,1]其实不对。把[1,1,5]的所有排列按字典序排出来是[1,1,5]、[1,5,1]、[5,1,1]。它当前是字典序最小的一个所以下一个是[1,5,1]。1.2 “字典序”是什么从字典查单词到数组比较字典序就是“像查英文词典那样排序”。两个单词谁排在前面取决于第一个不同的字母谁更小。数组比较也一样从左往右找到第一个不相等的位置谁的数字更小谁就在字典序中更靠前。举个例子[1,2,3] [1,3,2]因为第2位2 3[1,3,2] [2,1,3]因为第0位1 2所以对一个数组把所有可能的全排列从小到大排成一串[1,2,3]对应的排列顺序就是123、132、213、231、312、321。题目要做的就是找到当前排列在这串序列里的后一个元素。这里有一个容易混淆的点字典序和数字大小不完全是一回事。比如[1,2,3]按字典序排312排在321前面但按数字大小排序321是最大的三位数。为什么字典序里312 321因为第0位都是3比较第1位1 2。对数字314和321来说也是314 321但312和321的比较字典序只看逐位不看整体数值。所以这道题千万别往“数字大小”上想一定要回到“逐位比较”的字典序规则。1.3 为什么热题100里必须有它这道题能进热题100不是因为它难而是因为它处在“面试最爱的考察区间”难度适中、思路精巧、代码量小但能高效区分出“刷过题背过模板”和“真正理解排列规律”的候选人。从面试角度讲它至少覆盖了四个考点字典序的理解、贪心思路的运用、双指针操作数组、原地算法的实现习惯。而在Java面试中很多候选人习惯用ArrayList、Stream、StringBuilder这类工具类解决问题一旦要求就地在int[]上操作反而会手足无措这本身就是一种筛选。从工程角度讲排列生成是很多真实系统的底层工具。C标准库有std::next_permutationJava没有原生实现所以面试官让你手写一个并不算超纲。实际业务里排列枚举、组合搜索、搜索结果的排序切换、甚至是某些权限组合的全量遍历都会用到类似逻辑。2. 从观察规律到算法设计三步推导每一步都讲清“为什么”2.1 核心观察从右向左找第一个“升序对”先不急着写代码拿出一个排列比如[2,3,1]想一想“下一个更大的排列”应该怎么找。从字典序的定义出发两个排列比较优先看高位。想让排列变大就必须在某个高位i处放一个比nums[i]更大的数字然后让i右边的所有数字排成尽可能小的顺序。问题是这个“高位i”到底选在哪里关键规律是越靠右的位置权重越低。如果i选得太靠左就会把排列变得很大跳过中间很多排列。比如[2,3,1]如果动第0位把2换成3得到[3,2,1]跳跃太大实际上它的下一个排列是[3,1,2]只需要小幅调整。所以正确思路是从右往左找找到最靠右的、有潜力变大的位置。怎么判断“有潜力”看相邻两个元素。从右往左扫描找到第一个满足nums[i] nums[i1]的位置i。为什么是这个条件因为从i1到数组末尾这段区间是严格降序的。降序意味着什么意味着这段区间已经是它所有排列里最大的一个也就是说光调整i1之后的部分不可能得到更大的排列。要想变大必须动i。再用一个类比帮助理解这就像里程表的进位。末尾的数字已经到9了再走一步必须进位到前一位前一位到9了再进位到更前一位。你永远是从最右边的“还能变大”的档位开始变而不是直接去拨最左边的齿轮。这里有个细节要提醒扫描条件是nums[i] nums[i1]时继续向左移动等于的情况也要继续扫。因为相等时换过去也不会产生“更大于”的效果反而会破坏稳定性。后面讲重复元素时会再展开。2.2 关键第二步从右侧找“比nums[i]大的最小元素”找到位置i之后问题变成右侧区间里这么多数字应该把哪个换到i的位置上答案是从右往左找到第一个大于nums[i]的元素nums[j]交换它们。为什么是从右往左的第一个因为右侧区间本来就是降序的从右往左扫第一个遇到的“大于nums[i]”的元素恰恰就是所有大于nums[i]的元素里最小的那个。把它放到位置i既保证了新排列比当前排列大又保证增大幅度最小正好是“下一个”。这里有一个很经典的边界细节判断条件是nums[j] nums[i]时继续向左移动而不是。这个细节在[1,5,1]这种用例里会体现得很清楚i 0因为nums[0] 1 nums[1] 5从右往左找大于nums[0]的数j2时nums[2]1不满足继续j1时nums[1]5满足交换交换后数组变为[5,1,1]反转i11之后的所有元素实际只有[1,1]保持不变如果用而不是从右往左第一个“大于1”的数还是5因为位置2的1不大于1结果碰巧一样。但换个场景比如[1,1,5]i1nums[1]1 nums[2]5从右往左找大于1的数j2nums[2]5交换后是[1,5,1]反转位置2之后结果是[1,5,1]正确。那么什么时候和会不一样考虑[2,3,3,1]从右往左找升序对i1nums[1]3 nums[2]3?不对3 3是false。继续i0nums[0]2 nums[1]3所以i0从右往左找第一个大于nums[0]2的数j3nums[3]1不满足j2nums[2]3满足交换后[3,3,2,1]不对交换位置0和2[3,3,2,1]反转位置1之后所有元素[3,1,2,3]验证一下把[2,3,3,1]的所有排列排序它的下一个确实应该是[3,1,2,3]。如果用而不是从右往左找第一个大于2的数j会停在哪个位置还是2位置2的3结果一样。真正让和产生区别的是nums[i]本身在右边有相等的元素。比如[1,3,3,2]从右往左找升序对i013用时从右往左找第一个大于1的数j321交换[2,3,3,1]反转[3,3,1]得到[2,1,3,3]正确如果用了j321还是一样的。其实在这个算法里由于i的位置是“第一个非降序对”的左侧nums[i]一定严格小于nums[i1]而右侧是降序从右往左第一个“严格大于”和第一个“大于等于”在大多数情况下会落在同一个位置。真正的区别发生在极端的重复元素场景下但既然标准答案写的是那就按来这是一种防御性写法避免在边界上出幺蛾子。2.3 为什么最后一步是反转而不是排序交换完nums[i]和nums[j]之后数组左侧的i位置已经比原来更大了但此时得到的排列还不是“下一个”因为i右边的区间还保持着一个“草率”的降序状态随时可以变得更小。关键点在于交换之后i1到数组末尾依然是一个降序区间。原因很简单原来的区间从i1开始是严格降序的nums[j]是从右往左第一个大于nums[i]的元素所以它左边的元素都比它大它右边的元素都不大于nums[i]。把nums[i]放到位置j之后这个区间依然保持降序可能有相等元素。既然是一个降序区间我们只需要把它反转就能得到这段区间能组成的字典序最小的排列。反转一个降序数组得到升序数组升序排列就是所有排列中最小的那个。也就是说i位置已经“进位”到最合适的更大值剩下的部分全部重置为最小状态。这也解释了为什么最后一步用反转而不是排序。二者结果一样——都是把一段降序区间变成升序——但排序是O(n log n)反转是O(n)在面试官面前能看出你对数组结构的观察深度。很多人在这里直接调用Arrays.sort代码也能跑但在热题100这种追求最优解的语境里这是明显的减分项。另一种特殊情况是整个数组本身就是降序的比如[3,2,1]第一步找不到任何升序对。这说明当前排列已经是所有排列中的最后一个不存在“下一个更大的排列”。按题目要求直接反转整个数组得到[1,2,3]回到字典序最小的排列。这个逻辑和前面“反转降序区间”是统一的只是把区间扩大到了整个数组。3. Java实现原地算法、边界处理与复杂度分析3.1 标准解法代码实现下面是完整的Java实现也是我推荐在面试时写的版本public void nextPermutation(int[] nums) { int i nums.length - 2; // 第一步从右向左找第一个升序对 while (i 0 nums[i] nums[i 1]) { i--; } // 第二步找到比 nums[i] 大的最小元素并交换 if (i 0) { int j nums.length - 1; while (j 0 nums[j] nums[i]) { j--; } swap(nums, i, j); } // 第三步反转 i 之后的降序区间 reverse(nums, i 1); } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } private void reverse(int[] nums, int start) { int left start; int right nums.length - 1; while (left right) { swap(nums, left, right--); } }这段代码有几个设计得很巧妙的点。第一如果整个数组是降序第一步的i最终会变成-1此时跳过if块直接反转整个数组逻辑对且省代码第二把swap和reverse抽成独立方法主方法的三个步骤一目了然面试时也好讲思路第三变量名i、j不花哨但每个变量在面试讲述中都有明确含义i是“需要变动的最高位”j是“右侧最小的更大值”。3.2 边界条件与特殊场景数组长度小于等于1时没有任何排列变化空间代码应该什么都不做。length - 2为负数i的初始值就是-1第一步while循环条件直接不满足i 0为false跳过if调用reverse(nums, 0)。如果长度是0reverse里的right -1left 0while进不去安全如果长度是1right 0left 1while也进不去安全。标准解法天然处理了这些边界不需要额外写if (nums.length 1) return。但如果你觉得不放心加一句也无妨我更倾向于不写保持代码精简。全相等数组比如[1,1,1]或者[2,2,2,2]第一步会一路扫描到i -1因为nums[i] nums[i 1]始终成立。然后整体反转。由于所有元素相等反转后数组不变符合预期一个全等排列没有“下一个”回到最小排列就是它自己。最大值边界[3,2,1]已经讨论过返回[1,2,3]。最小值边界[1,2,3]正常走完第一步i1第二步j2交换得到[1,3,2]反转位置2之后的空区间结果正确。这些边界最好在面试时主动提一嘴比等面试官追问要加分。3.3 时间复杂度与空间复杂度时间复杂度是O(n)其中n是数组长度。三个步骤各自只有一次线性扫描第一步从右往左找到第一个升序对最坏情况下扫完整组第二步从右往左找到交换位置同样最多扫一遍第三步反转区间也是线性操作。三步加起来是O(3n)忽略常数就是O(n)。不需要嵌套循环也没有额外的排序操作这是整套算法的核心优势。空间复杂度是O(1)。整个算法只用了i、j、temp等固定数量的局部变量没有借助额外的数组、字符串或集合完全满足题目“原地修改、常数级额外空间”的硬性约束。可以和另一种错误思路对比。有人想先把数组复制一份找到它的全排列再取下一个这种思路可以吗可以但时间复杂度是O(n!)空间复杂度也是O(n!)完全不可能通过。还有人想到用TreeSet来维护排列顺序同样不可行。这个题目真正想考察的就是“不借助额外空间、在线性时间内完成”的贪心双指针思路。3.4 面试时的Java写法细节这段代码在面试时怎么写更稳妥我提几个实战经验。辅助方法命名要表意。swap、reverse这类名字是业界共识面试官扫一眼就懂。不要写什么s、r这种缩写也不要在一行里写太多逻辑。代码是给人看的尤其是面试场景你的代码同时也是你的“口头表达草稿”。注释写到步骤级别就够了。三个步骤对应三行关键注释每个注释标明这一步在做什么。没必要逐行注释那样反而显得你不自信。面试官问起细节时你再用语言补充“为什么要从右往左”即可。要不要在类里定义静态方法看场合。如果你是在力扣平台上写方法本身是实例方法辅助方法跟着写实例方法就好。如果你是在本地IDE演示可以定义成静态方法和数组工具类的使用习惯一致。优先级是保持代码能直接运行不要引入额外依赖不要在面试时花时间调整修饰符。4. 面试现场的高频追问与变体题4.1 追问一为什么最后用反转而不是Arrays.sort这是面试官最常用来判断你“懂不懂原理”的问题。想清楚应对策略不只是为了这一题而是为了展示你对算法结构的掌控力。正确的回答思路分两层。第一层算法本身已经保证了i1之后的区间是降序的降序区间反转一次就是升序而升序是这段区间能组成的最小排列所以反转足够了。第二层反转是O(n)排序是O(n log n)既然已知区间有序就没必要付出额外的时间成本。如果在面试时能顺手说出“这个区间是降序的所以反转之后的升序排列就是这个局部区间的最小排列”基本就说明你已经吃透了。还有一层更深的观察可以等面试官追问时再说在第二步交换前右侧区间是降序交换后它仍然是降序。这个“结构不变性”是整套算法的隐藏支点也是为什么可以用反转的原因。能主动说出这一句的候选人属于真正理解了这道题。4.2 追问二如果要求输出从当前排列开始的第k个排列怎么办这道题可以被改造成一个“生成器”。把nextPermutation看成迭代器调用一次得到下一个再调用一次得到下下个只要在循环里调用k次即可。public int[] kthPermutation(int[] nums, int k) { for (int count 0; count k; count) { nextPermutation(nums); } return nums; }这种实现思路很直观但不代表最优。如果k很大或者数组很长依次迭代的效率会比较低。更高效的做法是用康托展开或回溯逐位构造这是LeetCode 60“排列序列”考察的内容。不过面试时先把“基于nextPermutation生成全排列”这个思路说出来已经可以证明你能灵活运用这道题了。与之相关的一个经典追问是给定一个排列求它在所有全排列中的字典序排名也就是它的“逆康托展开”。这类问题在热题100里不常见但如果你想把这个知识点吃透可以作为延伸阅读。4.3 追问三输入不是数组而是一个整数怎么办这是LeetCode 556题的场景给定一个正整数n返回由n的数字重新排列组成的、字典序上大于n的最小整数。本质上就是“下一个排列”在整数场景的应用但多了两个额外限制结果是整数不能以0开头且不能超过int范围。把整数转成字符数组按同样的算法处理最后判断数值是否溢出即可public int nextGreaterElement(int n) { char[] arr String.valueOf(n).toCharArray(); int i arr.length - 2; while (i 0 arr[i] arr[i 1]) { i--; } if (i 0) { return -1; } int j arr.length - 1; while (j 0 arr[j] arr[i]) { j--; } swap(arr, i, j); reverse(arr, i 1); long ans Long.parseLong(new String(arr)); return ans Integer.MAX_VALUE ? -1 : (int) ans; } private void swap(char[] arr, int i, int j) { char temp arr[i]; arr[i] arr[j]; arr[j] temp; } private void reverse(char[] arr, int start) { int left start; int right arr.length - 1; while (left right) { swap(arr, left, right--); } }这里用long来接解析结果是为了防止中间结果溢出int比如输入2147483412这类数字转换后可能超过int范围。面试时能主动提到溢出处理说明你有生产环境的敏感性而不是只会刷题。4.4 追问四用全排列暴力解法和这个算法有什么区别如果对着一道题说“我可以先求出所有排列再找下一个”面试官可能会追问这两种方案的本质区别。对比如下维度全排列暴力法字典序贪心法时间复杂度O(n!)O(n)空间复杂度O(n!)O(1)是否原地否是是否适合大规模数据否是是否适合面试展示否是理论上[3,2,1]这种例子一眼就能看出“降序回到升序”很多人以为这道题只是在模拟“把最大的数移到最前”但这只是特例。真正写代码时你要保证任意排列都能正确处理这就是贪心算法的价值。5. 实战调试典型错误、测试用例与排查思路5.1 错误一从右往左找升序对时用nums[i] nums[i1]而不是nums[i] nums[i1]这是最常见的第一类错误多见于遗漏重复元素的场景。如果在扫描时只处理严格大于遇到相等元素会提前停下导致后续“找右侧更大元素”的逻辑出错。看一个具体例子[1,2,2,1]。正确算法应该这样跑从右往左找第一个升序对i1nums[1]2 nums[2]2?不成立继续i0nums[0]1 nums[1]2找到i0再从右往左找第一个大于1的元素j3nums[3]1不满足j2nums[2]2满足交换得到[2,2,1,1]不对交换位置0和2[2,2,1,1]反转位置1之后的所有元素[2,1,1,2]。验证所有排列1222的各种排列里1222的字典序下一个是2122这里有点绕还是用标准排列验证1,2,2的所有排列是 122, 212, 221。[1,2,2]的下一个应该是[2,1,2]但我们的数组是[1,2,2,1]吗不我举的例子是[1,2,2,1]它的排列数字是1,2,2,1不是一个干净的数字集合。假设数组是[1,2,2]正确算法i012j2nums[2]2 1交换[2,2,1]反转位置1之后为[2,1,2]反转后[2,1,2]。把1,2,2的所有排列列出来122、212、221122的下一个确实是212正确。这就是为什么要用的原因如果只处理严格大于当nums[i] nums[i1]时我们会认为这里还能交换但交换两个相等的数字没有意义还会扰乱后面的逻辑。5.2 错误二在第二步用nums[j] nums[i]而不是nums[j] nums[i]两类错误很像但踩坑场景不同。如果第二步用在重复元素存在时可能选错交换对象导致结果不是“下一个”而是“下下个”。例子[1,5,1]。正确算法我们前面算过i0j1nums[1]5 1交换得到[5,1,1]反转位置1之后为[5,1,1]。如果第二步用从右往左找第一个大于1的数j2时nums[2]11 1为false不能向左走j2出循环交换nums[0]和nums[2]结果[1,5,1]没有变化反转位置1之后为[1,1,5]完全错误。所以这里必须是才需要向右继续找。这个例子最好在面试时说给面试官听它比背条件更能体现你的理解深度。5.3 错误三交换之后对后半段排序而不是反转这种写法结果一般是对的但在两个维度上有问题。第一是效率排序是O(k log k)k是后半段的长度整体复杂度退化为O(n log n)不再满足该题“最优线性解”的预期。第二是面试追问风险面试官一定会问“为什么排序”如果你的回答是“这样保证最小的排列”他会追问“还有没有更快的办法”最后还是会引导到反转上。如果在面试时一时没想清楚写出排序也不至于算错但你要在回答追问前尽快想通反转的逻辑。更好的做法是主动说明“这里其实是一个降序区间反转就可以不需要排序。”一边说一边把代码改成reverse会让面试官看到你在思考而非机械复现。5.4 常用测试用例清单这里整理一组我平时刷这道题时常用的测试数据覆盖各种容易出错的场景建议你自己跑一下输入数组预期输出覆盖场景[1,2,3][1,3,2]基础用例从最小排列开始[3,2,1][1,2,3]最大排列整体反转[1,1,5][1,5,1]重复元素[1,5,1][5,1,1]查找右侧更大元素时的边界[2,3,1][3,1,2]非平凡的中间排列[1,3,2][2,1,3]右侧区间长度大于1[2,2,4,3][2,3,2,4]? 需要验证重复元素右侧降序区间第七个例子验证一下[2,2,4,3]从右往左找升序对i243?不成立i124成立。第二步找大于nums[1]2的最小元素j332成立交换位置1和3得到[2,3,4,2]反转位置2之后位置2和3的[4,2]反转为[2,4]结果是[2,3,2,4]。好预期是[2,3,2,4]表里写的[2,3,2,4]正确。5.5 调试时的一个实用技巧如果手边没有IDE或者一时想不出哪里写错了可以写一个小工具方法把数组转成字符串打印出来然后对照题目示例一步步走。我是这么调试的System.out.println(Arrays.toString(nums));在每一步操作之后打印一次对比和自己手算的结果。这个方法很土但在现场写代码时相当管用。面试时如果允许调试有些平台允许就大胆用如果不允许就在纸上手写推导也是锻炼思维的好机会。最后分享一个实操心得刷这道题的价值在实际面试中很容易被低估。它不像动态规划那样需要“顿悟”也不像图论那样有大量模板但它恰好处在“背模板”和“真理解”的分界线上。我见过不少候选人能写出标准解法但追问时答不上来“为什么右侧区间交换后仍是降序”这种问题。所以我个人的练习建议是不要满足于把代码默写出来而是尝试不看题解、从排列定义出发自己推导一遍再把整段思路讲给旁边的人听。能讲明白才是真的会了。