 求字典序后继的贪心算法)
LeetCode 31. 下一个排列Next Permutation题解原地 O(n) 求字典序后继的贪心算法【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术指南以本仓库leetcode 解题之路中 problems/31.next-permutation.md 为核心完整拆解 LeetCode 第 31 题「下一个排列」从回溯视角推导出从后往前找第一个递减位置 右侧最小更大值交换 尾部反转的线性算法并给出 JavaScript、Python3、CPP 三种可运行实现。读完本文你将掌握字典序排列后继问题的标准解法、其与全排列46/47、第 k 个排列60等排列家族题目的关系以及如何写出时间复杂度 O(n)、空间复杂度 O(1) 的原地解法。题目描述实现获取下一个排列的函数算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列则将数字重新排列成最小的排列即升序排列。必须原地修改只允许使用额外常数空间。以下是一些例子输入位于左侧列其相应输出位于右侧列1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1三个例子分别覆盖了三种典型场景普通递增序列交换相邻元素即得后继、完全递减序列不存在后继需返回升序最小排列、含重复元素的序列说明算法必须正确处理重复值。题目有两个硬性约束直接决定了算法选型必须原地修改只能操作传入的nums数组不能新建数组再整体赋值只允许使用额外常数空间排除一切需要 O(n) 辅助空间的方案。前置知识与考察点本题虽被归类为中等难度仓库 collections/medium.md 中亦有收录但考察的知识点相当综合回溯法仓库 thinkings/backtrack.md 指出回溯本质是穷举所有可能的试错过程可抽象为一棵 N 叉树全排列问题的解空间大小是 n!。虽然本题最终用贪心 双指针解决但回溯思维是理解下一个排列语义的钥匙贪心思想要得到下一个更大的排列且增幅最小需要选取恰当的交换对象双指针 / 反转在有序区间内用首尾交换实现反转是本题收尾步骤的核心技巧。核心思路从暴力回溯到字典序后继为什么暴力生成全排列不可行符合直觉的方法是按顺序求出所有的排列参考 problems/46.permutations.md 中的回溯实现如果当前排列等于nums直接取下一个。但这种做法有两个致命问题时间复杂度为O(n!)n 稍大即不可接受需要把整个排列空间保存在结果集中不符合 constant space常数空间的要求——题目要求直接修改原数组。因此必须寻找不依赖全排列枚举的定向构造方法。回溯视角从后往前思考我们可以以回溯的角度来思考这个问题即从后往前思考。回溯的本质是逐步尝试每个位置可以放置的数字当我们走到最后一个数字时如果它无法构成更大的排列就退回上一步尝试其他选择。让我们先回溯一次即思考最后一个数字是如何被添加的由于这个时候可以选择的元素只有 2我们无法组成更大的排列我们继续回溯直到如图我们发现可以交换 4 和 2但这样会变小因此我们不能进行交换。接下来碰到了 1我们有两个选择1 和 2 进行交换1 和 4 进行交换。两种交换都能使得结果更大但是和 2 交换能够使得增值最小也就是题目要求的下一个更大的排列效果。因此我们将 1 和 2 进行交换贪心为什么交换低位而不是更高位还需要继续往高位看么不需要因为交换高位得到的增幅一定比交换低位大这是一个贪心的思想——要得到下一个更大的排列增幅越小越好因此我们应该优先在尽可能低靠右的位置上做文章而不是轻易动高位。关键洞察第一个可交换的回溯点就是从后往前第一个递减的值从上面的回溯过程可以提炼出本题最核心的洞察从后往前扫描找到第一个满足nums[i] nums[i 1]的位置i这个i就是第一个可以交换的回溯点。为什么因为i右侧的所有元素构成一个从后往前非递减的序列即非严格递减此时右侧已经没有任何内部交换能产生更大排列只能把更高位的nums[i]换掉。从代码结构看详见下文实现一旦i不存在说明整个数组本身已经是从大到小的最大排列此时直接反转整个数组得到升序最小排列即可。如何保证增幅最小交换时需要在i右侧找到从右边起第一个大于nums[i]的数即大于nums[i]的最小值与之交换——因为如果交换的数字比nums[i]还小结果会变小不符合题意。交换完成后还需要保证i右侧的序列是升序最小的字典序。注意到i后面的数在交换前已经是从大到小排列非严格递减交换后依然保持递减序此时我们只需要用双指针首尾交换reverse即可而不需要真正地排序。补充证明i后面的数一定是从大到小排好序了吗当然否则我们找到第一个可以交换的回溯点就不是i了和i是第一个可以交换的回溯点矛盾。因为第一个可以交换的回溯点其实就是从后往前第一个递减的值。这一性质保证了尾部区间用双指针反转即可完成升序化复杂度从 O(n log n) 降至 O(n)。算法步骤逐步分解综上标准解法可归纳为四步找分割点从后往前扫描找到第一个满足nums[i] nums[i 1]的位置i判是否最大排列若i 0说明整个序列是递减的已是最大排列跳到第 4 步直接整体反转交换从右往左找到第一个大于nums[i]的位置j交换nums[i]与nums[j]反转尾部将[i 1, len - 1]区间的元素反转升序化得到字典序意义上的下一个最小更大排列。以1,2,3为例走一遍从后往前找到i 1nums[1] 2 nums[2] 3右侧第一个大于 2 的是 3交换得1,3,2再反转[2,2]区间单元素无需操作结果为1,3,2与题目示例一致。以3,2,1为例找不到任何nums[i] nums[i 1]即i -1直接整体反转得1,2,3与题目示例一致。三种语言实现原文档提供了 JavaScript、Python3、CPP 三种实现以下代码可直接复制运行均满足原地修改与常数空间约束。JavaScript/* * lc appleetcode id31 langjavascript * * [31] Next Permutation */ function reverseRange(A, i, j) { while (i j) { const temp A[i]; A[i] A[j]; A[j] temp; i; j--; } } /** * param {number[]} nums * return {void} Do not return anything, modify nums in-place instead. */ var nextPermutation function (nums) { // 时间复杂度O(n) 空间复杂度O(1) if (nums null || nums.length 1) return; let i nums.length - 2; // 从后往前找到第一个降序的,相当于找到了我们的回溯点 while (i -1 nums[i 1] nums[i]) i--; // 如果找了就swap if (i -1) { let j nums.length - 1; // 找到从右边起第一个大于nums[i]的并将其和nums[i]进行交换 // 因为如果交换的数字比nums[i]还要小肯定不符合题意 while (nums[j] nums[i]) j--; const temp nums[i]; nums[i] nums[j]; nums[j] temp; } // 最后我们只需要将剩下的元素从左到右依次填入当前最小的元素就可以保证是大于当前排列的最小值了 // [i 1, A.length -1]的元素进行反转 reverseRange(nums, i 1, nums.length - 1); };Python3class Solution: def nextPermutation(self, nums: List[int]) - None: i len(nums) - 2 while i 0 and nums[i] nums[i 1]: i - 1 if i 0: j len(nums) - 1 while j 0 and nums[i] nums[j]: j - 1 nums[i], nums[j] nums[j], nums[i] left, right i 1, len(nums) - 1 while left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1CPPclass Solution { public: void nextPermutation(vectorint nums) { int i nums.size() - 2, j nums.size() - 1; while (i 0 nums[i] nums[i 1]) --i; if (i 0) { while (j i nums[j] nums[i]) --j; swap(nums[i], nums[j]); } reverse(nums.begin() i 1, nums.end()); } };代码细节对照代码片段对应算法步骤注意点while (nums[i 1] nums[i]) i--找分割点用跳过相等元素保证重复值场景下分割点取到最右侧while (nums[j] nums[i]) j--找右侧最小更大值从右往左扫第一个大于nums[i]的值即最小更大值reverseRange(nums, i 1, nums.length - 1)尾部升序化尾部必为递减序双指针反转即可无需排序值得注意的是i -1最大排列时reverseRange(nums, 0, len - 1)恰好将整个数组反转回升序最小排列因此三种实现都不需要为不存在后继单独分支处理反转范围——这一设计非常精妙。复杂度分析令n为数组长度时间复杂度O(n)。扫描分割点最坏 O(n)找交换点最坏 O(n)尾部反转 O(n/2)三个线性步骤顺序执行总复杂度为 O(n)空间复杂度O(1)。只使用常数个索引变量与临时交换变量完全符合题目只允许使用额外常数空间的约束。这一结论可直接从代码结构验证全程无递归、无辅助数据结构仅有i、j与temp三个标量。边界情况与重复元素处理本题的边界情况很容易出错务必用多组数据自测单元素 / 空数组nums null || nums.length 1时直接返回无需任何操作完全递减最大排列如3,2,1找不到分割点整体反转得到升序最小排列含重复元素如1,1,5 → 1,5,1、1,5,1 → 5,1,1。关键在于扫描时使用非严格比较使分割点落在相等区间的最左侧交换时同样用跳过相等值保证重复元素下仍能得到字典序紧邻的后继交换后尾部仍需反转交换只保证nums[i]变大若尾部仍为递减序必须反转才能得到最小更大排列。与排列家族题目的横向对比仓库中围绕排列有一组互相呼应、层层递进的题目理解本题后建议串联学习题目问题形态解法与本题关系46. 全排列生成无重复序列的全部排列回溯O(n!)暴力解法的上限参照本题是对其解空间的定向跳跃47. 全排列 II含重复数字生成不重复全排列回溯 排序去重nums[i] nums[i - 1] visited[i - 1]剪枝与本题共用处理重复元素的心智模型31. 下一个排列本题求字典序中紧邻的下一个排列贪心 双指针反转O(n)排列问题中最基础的 O(n) 线性解法60. 第 k 个排列按字典序求第 k 个排列阶乘分组定位math.factorialO(n²)problems/60.permutation-sequence.md 明确指出 LeetCode 排列题分为三类生成全排列46/47、生成下一个排列31、生成第 k 个排列60本题是连接全枚举与定向构造的桥梁其中 problems/60.permutation-sequence.md 的这段归类说明LeetCode 上关于排列的题目目前主要有三种类型非常值得阅读它揭示了这三类题目在解空间上的递进关系全排列枚举解空间 → 在解空间中定位紧邻后继 → 在解空间中按序数直接构造。关键点总结原文档对本题给出了三条凝练的经验这也是面试复盘时的高频考点写几个例子通常会帮助理解问题的规律比如把1,2,3的全排列按字典序写出观察相邻两项的变化规律规律自然浮现在有序数组中首尾指针不断交换位置即可实现 reverse这是反转区间的高效手法时间复杂度 O(n)、空间 O(1)比sort更适合本题的降序尾部找到从右边起第一个大于nums[i]的数并将其和nums[i]进行交换这是保证增幅最小的关键交换对象必须是右侧大于nums[i]的最小值。此外仓库还提供了本题的可视化资源assets/drawio/31.next-permutation.drawiodraw.io 流程图以及本文沿用的 assets/problems/31.next-permutation-2.jpg、assets/problems/31.next-permutation-3.jpg、assets/problems/31.next-permutation-4.jpg 三张过程示意图适合配合本文章反复推演。延伸思考若题目要求改为上一个排列只需把算法中的大小比较全部反向找从后往前第一个递增点、交换右侧最大更小值即可对称地解决本题的 O(n) 线性复杂度来源于尾部区间的非严格递减性质这个性质是回溯推导的直接推论——理解推导过程比背代码更重要实际工程中字典序后继思想还被用于生成组合、子集等对象的全量枚举如 next_combination 类算法掌握本题的思维框架后可以触类旁通。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/19 20:25:05 · 阅读 1.2k LeetCode 31. 下一个排列（Next Permutation）题解：原地 O(n) 求字典序后继的贪心算法
LeetCode 31. 下一个排列Next Permutation题解原地 O(n) 求字典序后继的贪心算法【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术指南以本仓库leetcode 解题之路中 problems/31.next-permutation.md 为核心完整拆解 LeetCode 第 31 题「下一个排列」从回溯视角推导出从后往前找第一个递减位置 右侧最小更大值交换 尾部反转的线性算法并给出 JavaScript、Python3、CPP 三种可运行实现。读完本文你将掌握字典序排列后继问题的标准解法、其与全排列46/47、第 k 个排列60等排列家族题目的关系以及如何写出时间复杂度 O(n)、空间复杂度 O(1) 的原地解法。题目描述实现获取下一个排列的函数算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列则将数字重新排列成最小的排列即升序排列。必须原地修改只允许使用额外常数空间。以下是一些例子输入位于左侧列其相应输出位于右侧列1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1三个例子分别覆盖了三种典型场景普通递增序列交换相邻元素即得后继、完全递减序列不存在后继需返回升序最小排列、含重复元素的序列说明算法必须正确处理重复值。题目有两个硬性约束直接决定了算法选型必须原地修改只能操作传入的nums数组不能新建数组再整体赋值只允许使用额外常数空间排除一切需要 O(n) 辅助空间的方案。前置知识与考察点本题虽被归类为中等难度仓库 collections/medium.md 中亦有收录但考察的知识点相当综合回溯法仓库 thinkings/backtrack.md 指出回溯本质是穷举所有可能的试错过程可抽象为一棵 N 叉树全排列问题的解空间大小是 n!。虽然本题最终用贪心 双指针解决但回溯思维是理解下一个排列语义的钥匙贪心思想要得到下一个更大的排列且增幅最小需要选取恰当的交换对象双指针 / 反转在有序区间内用首尾交换实现反转是本题收尾步骤的核心技巧。核心思路从暴力回溯到字典序后继为什么暴力生成全排列不可行符合直觉的方法是按顺序求出所有的排列参考 problems/46.permutations.md 中的回溯实现如果当前排列等于nums直接取下一个。但这种做法有两个致命问题时间复杂度为O(n!)n 稍大即不可接受需要把整个排列空间保存在结果集中不符合 constant space常数空间的要求——题目要求直接修改原数组。因此必须寻找不依赖全排列枚举的定向构造方法。回溯视角从后往前思考我们可以以回溯的角度来思考这个问题即从后往前思考。回溯的本质是逐步尝试每个位置可以放置的数字当我们走到最后一个数字时如果它无法构成更大的排列就退回上一步尝试其他选择。让我们先回溯一次即思考最后一个数字是如何被添加的由于这个时候可以选择的元素只有 2我们无法组成更大的排列我们继续回溯直到如图我们发现可以交换 4 和 2但这样会变小因此我们不能进行交换。接下来碰到了 1我们有两个选择1 和 2 进行交换1 和 4 进行交换。两种交换都能使得结果更大但是和 2 交换能够使得增值最小也就是题目要求的下一个更大的排列效果。因此我们将 1 和 2 进行交换贪心为什么交换低位而不是更高位还需要继续往高位看么不需要因为交换高位得到的增幅一定比交换低位大这是一个贪心的思想——要得到下一个更大的排列增幅越小越好因此我们应该优先在尽可能低靠右的位置上做文章而不是轻易动高位。关键洞察第一个可交换的回溯点就是从后往前第一个递减的值从上面的回溯过程可以提炼出本题最核心的洞察从后往前扫描找到第一个满足nums[i] nums[i 1]的位置i这个i就是第一个可以交换的回溯点。为什么因为i右侧的所有元素构成一个从后往前非递减的序列即非严格递减此时右侧已经没有任何内部交换能产生更大排列只能把更高位的nums[i]换掉。从代码结构看详见下文实现一旦i不存在说明整个数组本身已经是从大到小的最大排列此时直接反转整个数组得到升序最小排列即可。如何保证增幅最小交换时需要在i右侧找到从右边起第一个大于nums[i]的数即大于nums[i]的最小值与之交换——因为如果交换的数字比nums[i]还小结果会变小不符合题意。交换完成后还需要保证i右侧的序列是升序最小的字典序。注意到i后面的数在交换前已经是从大到小排列非严格递减交换后依然保持递减序此时我们只需要用双指针首尾交换reverse即可而不需要真正地排序。补充证明i后面的数一定是从大到小排好序了吗当然否则我们找到第一个可以交换的回溯点就不是i了和i是第一个可以交换的回溯点矛盾。因为第一个可以交换的回溯点其实就是从后往前第一个递减的值。这一性质保证了尾部区间用双指针反转即可完成升序化复杂度从 O(n log n) 降至 O(n)。算法步骤逐步分解综上标准解法可归纳为四步找分割点从后往前扫描找到第一个满足nums[i] nums[i 1]的位置i判是否最大排列若i 0说明整个序列是递减的已是最大排列跳到第 4 步直接整体反转交换从右往左找到第一个大于nums[i]的位置j交换nums[i]与nums[j]反转尾部将[i 1, len - 1]区间的元素反转升序化得到字典序意义上的下一个最小更大排列。以1,2,3为例走一遍从后往前找到i 1nums[1] 2 nums[2] 3右侧第一个大于 2 的是 3交换得1,3,2再反转[2,2]区间单元素无需操作结果为1,3,2与题目示例一致。以3,2,1为例找不到任何nums[i] nums[i 1]即i -1直接整体反转得1,2,3与题目示例一致。三种语言实现原文档提供了 JavaScript、Python3、CPP 三种实现以下代码可直接复制运行均满足原地修改与常数空间约束。JavaScript/* * lc appleetcode id31 langjavascript * * [31] Next Permutation */ function reverseRange(A, i, j) { while (i j) { const temp A[i]; A[i] A[j]; A[j] temp; i; j--; } } /** * param {number[]} nums * return {void} Do not return anything, modify nums in-place instead. */ var nextPermutation function (nums) { // 时间复杂度O(n) 空间复杂度O(1) if (nums null || nums.length 1) return; let i nums.length - 2; // 从后往前找到第一个降序的,相当于找到了我们的回溯点 while (i -1 nums[i 1] nums[i]) i--; // 如果找了就swap if (i -1) { let j nums.length - 1; // 找到从右边起第一个大于nums[i]的并将其和nums[i]进行交换 // 因为如果交换的数字比nums[i]还要小肯定不符合题意 while (nums[j] nums[i]) j--; const temp nums[i]; nums[i] nums[j]; nums[j] temp; } // 最后我们只需要将剩下的元素从左到右依次填入当前最小的元素就可以保证是大于当前排列的最小值了 // [i 1, A.length -1]的元素进行反转 reverseRange(nums, i 1, nums.length - 1); };Python3class Solution: def nextPermutation(self, nums: List[int]) - None: i len(nums) - 2 while i 0 and nums[i] nums[i 1]: i - 1 if i 0: j len(nums) - 1 while j 0 and nums[i] nums[j]: j - 1 nums[i], nums[j] nums[j], nums[i] left, right i 1, len(nums) - 1 while left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1CPPclass Solution { public: void nextPermutation(vectorint nums) { int i nums.size() - 2, j nums.size() - 1; while (i 0 nums[i] nums[i 1]) --i; if (i 0) { while (j i nums[j] nums[i]) --j; swap(nums[i], nums[j]); } reverse(nums.begin() i 1, nums.end()); } };代码细节对照代码片段对应算法步骤注意点while (nums[i 1] nums[i]) i--找分割点用跳过相等元素保证重复值场景下分割点取到最右侧while (nums[j] nums[i]) j--找右侧最小更大值从右往左扫第一个大于nums[i]的值即最小更大值reverseRange(nums, i 1, nums.length - 1)尾部升序化尾部必为递减序双指针反转即可无需排序值得注意的是i -1最大排列时reverseRange(nums, 0, len - 1)恰好将整个数组反转回升序最小排列因此三种实现都不需要为不存在后继单独分支处理反转范围——这一设计非常精妙。复杂度分析令n为数组长度时间复杂度O(n)。扫描分割点最坏 O(n)找交换点最坏 O(n)尾部反转 O(n/2)三个线性步骤顺序执行总复杂度为 O(n)空间复杂度O(1)。只使用常数个索引变量与临时交换变量完全符合题目只允许使用额外常数空间的约束。这一结论可直接从代码结构验证全程无递归、无辅助数据结构仅有i、j与temp三个标量。边界情况与重复元素处理本题的边界情况很容易出错务必用多组数据自测单元素 / 空数组nums null || nums.length 1时直接返回无需任何操作完全递减最大排列如3,2,1找不到分割点整体反转得到升序最小排列含重复元素如1,1,5 → 1,5,1、1,5,1 → 5,1,1。关键在于扫描时使用非严格比较使分割点落在相等区间的最左侧交换时同样用跳过相等值保证重复元素下仍能得到字典序紧邻的后继交换后尾部仍需反转交换只保证nums[i]变大若尾部仍为递减序必须反转才能得到最小更大排列。与排列家族题目的横向对比仓库中围绕排列有一组互相呼应、层层递进的题目理解本题后建议串联学习题目问题形态解法与本题关系46. 全排列生成无重复序列的全部排列回溯O(n!)暴力解法的上限参照本题是对其解空间的定向跳跃47. 全排列 II含重复数字生成不重复全排列回溯 排序去重nums[i] nums[i - 1] visited[i - 1]剪枝与本题共用处理重复元素的心智模型31. 下一个排列本题求字典序中紧邻的下一个排列贪心 双指针反转O(n)排列问题中最基础的 O(n) 线性解法60. 第 k 个排列按字典序求第 k 个排列阶乘分组定位math.factorialO(n²)problems/60.permutation-sequence.md 明确指出 LeetCode 排列题分为三类生成全排列46/47、生成下一个排列31、生成第 k 个排列60本题是连接全枚举与定向构造的桥梁其中 problems/60.permutation-sequence.md 的这段归类说明LeetCode 上关于排列的题目目前主要有三种类型非常值得阅读它揭示了这三类题目在解空间上的递进关系全排列枚举解空间 → 在解空间中定位紧邻后继 → 在解空间中按序数直接构造。关键点总结原文档对本题给出了三条凝练的经验这也是面试复盘时的高频考点写几个例子通常会帮助理解问题的规律比如把1,2,3的全排列按字典序写出观察相邻两项的变化规律规律自然浮现在有序数组中首尾指针不断交换位置即可实现 reverse这是反转区间的高效手法时间复杂度 O(n)、空间 O(1)比sort更适合本题的降序尾部找到从右边起第一个大于nums[i]的数并将其和nums[i]进行交换这是保证增幅最小的关键交换对象必须是右侧大于nums[i]的最小值。此外仓库还提供了本题的可视化资源assets/drawio/31.next-permutation.drawiodraw.io 流程图以及本文沿用的 assets/problems/31.next-permutation-2.jpg、assets/problems/31.next-permutation-3.jpg、assets/problems/31.next-permutation-4.jpg 三张过程示意图适合配合本文章反复推演。延伸思考若题目要求改为上一个排列只需把算法中的大小比较全部反向找从后往前第一个递增点、交换右侧最大更小值即可对称地解决本题的 O(n) 线性复杂度来源于尾部区间的非严格递减性质这个性质是回溯推导的直接推论——理解推导过程比背代码更重要实际工程中字典序后继思想还被用于生成组合、子集等对象的全量枚举如 next_combination 类算法掌握本题的思维框架后可以触类旁通。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考