企业官网建设流程全解析

LeetCode 31 Next Permutation 全解析：从 O(n!) 暴力枚举到 O(n) 贪心双指针

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

导读

本文围绕 LeetCode 经典中等题Next Permutation（下一个排列）展开，系统讲解字典序排列的核心概念、两种解题路径（O(n!·n) 暴力枚举与 O(n) 贪心双指针），并结合本仓库（LeetCode Solutions）中的多语言实现与关联题解，给出可复制、可运行的完整代码。读完本文，你将掌握"如何就地（in-place）求出字典序下一个排列"的标准算法，并理解为什么贪心解法是唯一可行的工程化方案。

1. 前置知识（Prerequisites）

在动手解决本题之前，建议先熟练以下三块基础能力，它们也是后续贪心解法的直接工具：

• 数组操作（Array Manipulation）：能够熟练进行就地交换（swap）与子数组反转（reverse）；
• 双指针技术（Two Pointers Technique）：使用左右指针相向移动来反转子数组；
• 字典序（Lexicographic Ordering）：理解序列之间如何按字典序比较和排序——这与字符串按字符顺序比较的规则完全一致。

字典序的直观含义：把数组视为一个"数字/字符串"，从左到右逐位比较，第一个出现差异的位置决定大小。例如[1, 2, 3] < [1, 3, 2]，因为第二位2 < 3。"下一个排列"指的就是：在所有排列的字典序排序中，紧跟当前排列之后的那一个；如果当前已是最大排列，则回到最小排列（即升序排列）。

提示：本仓库的 articles/permutations.md 与 articles/permutations-ii.md 详细讲解了全排列的生成（含去重），是理解本文暴力法的基础；java/0046-permutations.java 与 java/0047-permutations-ii.java 给出了对应源码。

2. 解法一：暴力法（Brute Force）

2.1 直觉（Intuition）

最直接的想法是：生成数组的全部排列，按字典序排序，在排序结果中找到当前排列的位置，返回其后一个排列；如果当前已是最后一个排列，则回绕（wrap around）到第一个排列。

这种方法的优点是概念上完全忠实于"下一个排列"的定义，缺点是极其低效——排列数量是 n!，对稍大的 n 就会爆炸，因此它仅用于帮助理解题意，实际竞赛与工程中不可用。

2.2 算法步骤（Algorithm）

1. 生成输入数组的全部唯一排列；
2. 将这些排列按字典序排序；
3. 在有序列表中找到当前数组的位置；
4. 返回列表中的下一个排列（若已到末尾则回绕到第一个）；
5. 将结果拷贝回原数组（满足题目"就地修改"的要求）。

2.3 多语言实现

以下实现均在生成排列时通过"跳过重复值"来保证唯一性，排序后逐个比对当前数组：

class Solution: def nextPermutation(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ permutations = self.permute(nums[:]) permutations.sort() for i, p in enumerate(permutations): if p == nums: nextP = permutations[(i + 1) % len(permutations)] for j in range(len(nums)): nums[j] = nextP[j] break def permute(self, nums: List[int]) -> List[List[int]]: res = [] def dfs(i): if i == len(nums): res.append(nums.copy()) return for j in range(i, len(nums)): if j > i and nums[i] == nums[j]: continue nums[i], nums[j] = nums[j], nums[i] dfs(i + 1) for j in range(len(nums) - 1, i, -1): nums[j], nums[i] = nums[i], nums[j] nums.sort() dfs(0) return res

public class Solution { public void nextPermutation(int[] nums) { List<List<Integer>> perms = permute(nums.clone()); Collections.sort(perms, (a, b) -> { for (int i = 0; i < a.size(); i++) { int diff = a.get(i) - b.get(i); if (diff != 0) return diff; } return 0; }); for (int i = 0; i < perms.size(); i++) { List<Integer> p = perms.get(i); boolean match = true; for (int j = 0; j < nums.length; j++) { if (p.get(j) != nums[j]) { match = false; break; } } if (match) { List<Integer> next = perms.get((i + 1) % perms.size()); for (int j = 0; j < nums.length; j++) { nums[j] = next.get(j); } return; } } } private List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(nums); boolean[] used = new boolean[nums.length]; List<Integer> path = new ArrayList<>(); dfs(nums, used, path, res); return res; } private void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) { if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++) { if (used[i]) continue; if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; used[i] = true; path.add(nums[i]); dfs(nums, used, path, res); path.remove(path.size() - 1); used[i] = false; } } }

class Solution { public: void nextPermutation(vector<int>& nums) { auto perms = permute(nums); sort(perms.begin(), perms.end()); for (int i = 0; i < perms.size(); i++) { if (perms[i] == nums) { auto& next = perms[(i + 1) % perms.size()]; nums = next; return; } } } private: vector<vector<int>> permute(vector<int> nums) { sort(nums.begin(), nums.end()); vector<vector<int>> res; vector<int> path; vector<bool> used(nums.size(), false); function<void()> dfs = [&]() { if (path.size() == nums.size()) { res.push_back(path); return; } for (int i = 0; i < nums.size(); i++) { if (used[i]) continue; if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; used[i] = true; path.push_back(nums[i]); dfs(); path.pop_back(); used[i] = false; } }; dfs(); return res; } };

class Solution { /** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */ nextPermutation(nums) { const permute = (arr) => { const res = []; arr.sort((a, b) => a - b); const used = Array(arr.length).fill(false); const path = []; const dfs = () => { if (path.length === arr.length) { res.push([...path]); return; } for (let i = 0; i < arr.length; i++) { if (used[i]) continue; if (i > 0 && arr[i] === arr[i - 1] && !used[i - 1]) continue; used[i] = true; path.push(arr[i]); dfs(); path.pop(); used[i] = false; } }; dfs(); return res; }; const perms = permute([...nums]); perms.sort((a, b) => { for (let i = 0; i < a.length; i++) { if (a[i] !== b[i]) return a[i] - b[i]; } return 0; }); for (let i = 0; i < perms.length; i++) { const p = perms[i]; if (p.every((v, j) => v === nums[j])) { const next = perms[(i + 1) % perms.length]; for (let j = 0; j < nums.length; j++) { nums[j] = next[j]; } break; } } } }

public class Solution { public void NextPermutation(int[] nums) { var perms = Permute((int[])nums.Clone()); perms.Sort((a, b) => { for (int i = 0; i < a.Count; i++) { int diff = a[i] - b[i]; if (diff != 0) return diff; } return 0; }); for (int i = 0; i < perms.Count; i++) { var p = perms[i]; bool match = true; for (int j = 0; j < nums.Length; j++) { if (p[j] != nums[j]) { match = false; break; } } if (match) { var next = perms[(i + 1) % perms.Count]; for (int j = 0; j < nums.Length; j++) { nums[j] = next[j]; } return; } } } private List<List<int>> Permute(int[] nums) { Array.Sort(nums); var res = new List<List<int>>(); var used = new bool[nums.Length]; var path = new List<int>(); void Dfs() { if (path.Count == nums.Length) { res.Add(new List<int>(path)); return; } for (int i = 0; i < nums.Length; i++) { if (used[i]) continue; if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; used[i] = true; path.Add(nums[i]); Dfs(); path.RemoveAt(path.Count - 1); used[i] = false; } } Dfs(); return res; } }

func nextPermutation(nums []int) { perms := permute(append([]int{}, nums...)) sort.Slice(perms, func(a, b int) bool { for i := 0; i < len(perms[a]); i++ { if perms[a][i] != perms[b][i] { return perms[a][i] < perms[b][i] } } return false }) for i := 0; i < len(perms); i++ { match := true for j := 0; j < len(nums); j++ { if perms[i][j] != nums[j] { match = false break } } if match { next := perms[(i+1)%len(perms)] copy(nums, next) return } } } func permute(nums []int) [][]int { sort.Ints(nums) var res [][]int used := make([]bool, len(nums)) var path []int var dfs func() dfs = func() { if len(path) == len(nums) { res = append(res, append([]int{}, path...)) return } for i := 0; i < len(nums); i++ { if used[i] { continue } if i > 0 && nums[i] == nums[i-1] && !used[i-1] { continue } used[i] = true path = append(path, nums[i]) dfs() path = path[:len(path)-1] used[i] = false } } dfs() return res }

class Solution { fun nextPermutation(nums: IntArray) { val perms = permute(nums.clone()) perms.sortWith { a, b -> for (i in a.indices) { if (a[i] != b[i]) return@sortWith a[i] - b[i] } 0 } for (i in perms.indices) { var match = true for (j in nums.indices) { if (perms[i][j] != nums[j]) { match = false break } } if (match) { val next = perms[(i + 1) % perms.size] for (j in nums.indices) { nums[j] = next[j] } return } } } private fun permute(nums: IntArray): MutableList<IntArray> { nums.sort() val res = mutableListOf<IntArray>() val used = BooleanArray(nums.size) val path = mutableListOf<Int>() fun dfs() { if (path.size == nums.size) { res.add(path.toIntArray()) return } for (i in nums.indices) { if (used[i]) continue if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue used[i] = true path.add(nums[i]) dfs() path.removeAt(path.size - 1) used[i] = false } } dfs() return res } }

class Solution { func nextPermutation(_ nums: inout [Int]) { var perms = permute(nums) perms.sort { a, b in for i in 0..<a.count { if a[i] != b[i] { return a[i] < b[i] } } return false } for i in 0..<perms.count { var match = true for j in 0..<nums.count { if perms[i][j] != nums[j] { match = false break } } if match { let next = perms[(i + 1) % perms.count] for j in 0..<nums.count { nums[j] = next[j] } return } } } private func permute(_ nums: [Int]) -> [[Int]] { var nums = nums.sorted() var res = [[Int]]() var used = Array(repeating: false, count: nums.count) var path = [Int]() func dfs() { if path.count == nums.count { res.append(path) return } for i in 0..<nums.count { if used[i] { continue } if i > 0 && nums[i] == nums[i - 1] && !used[i - 1] { continue } used[i] = true path.append(nums[i]) dfs() path.removeLast() used[i] = false } } dfs() return res } }

impl Solution { pub fn next_permutation(nums: &mut Vec<i32>) { let perms = Self::permute(nums.clone()); let mut perms = perms; perms.sort(); for i in 0..perms.len() { if perms[i] == *nums { let next = &perms[(i + 1) % perms.len()]; nums.copy_from_slice(next); return; } } } fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> { let mut nums = nums; nums.sort(); let mut res = Vec::new(); let mut used = vec![false; nums.len()]; let mut path = Vec::new(); fn dfs(nums: &[i32], used: &mut Vec<bool>, path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) { if path.len() == nums.len() { res.push(path.clone()); return; } for i in 0..nums.len() { if used[i] { continue; } if i > 0 && nums[i] == nums[i - 1] && !used[i - 1] { continue; } used[i] = true; path.push(nums[i]); dfs(nums, used, path, res); path.pop(); used[i] = false; } } dfs(&nums, &mut used, &mut path, &mut res); res } }

仓库佐证：暴力"反复调用 nextPermutation"的思路在 java/0060-permutation-sequence.java 的注释中有直接体现——该题（第 k 个排列）的暴力解法即是从升序排列开始连续调用 nextPermutation k-1 次，注释明确标注"similar to Next Permutation problem no.31"并指出该做法会超时（TLE）。

2.4 复杂度分析（Time & Space Complexity）

• 时间复杂度：O(n! · n)—— 生成 n! 个排列，每个排列排序/比对需要 O(n)；
• 空间复杂度：O(n! · n)—— 需要存储全部排列。

显然，任何超出玩具规模（n ≥ 10 左右）的输入都会让该方案不可行，因此必须转向下一节的贪心解法。

3. 解法二：贪心 + 双指针（Greedy）

3.1 直觉（Intuition）

要得到字典序下一个更大的排列，需要做能让数组值增大的最小改动。核心洞察是：找到最靠右的、能够增大的位置。

从右向左扫描，找到第一个比其右侧邻居小的元素（记为pivot）。由于pivot右侧是一个"最长递减后缀"，pivot是唯一可以变大以产生更大排列的位。接着，在pivot右侧找到大于 pivot 的最小元素与之交换——这样既保证变大，又保证增量最小。

交换之后，pivot右侧原本是递减序列；为了让"从 pivot 位开始的新排列尽可能小"，需要把该后缀反转成升序。若从头到尾都不存在这样的pivot（整个数组为递减序列，即最大排列），则把整个数组反转得到最小排列（满足题目的回绕要求）。

3.2 算法步骤（Algorithm）

1. 从倒数第二个元素向左扫描，找到第一个满足nums[i] < nums[i+1]的下标i；
2. 若存在这样的i：
   • 从最右侧向左扫描，找到第一个满足nums[j] > nums[i]的下标j；
   • 交换nums[i]与nums[j]；
3. 反转子数组nums[i+1 .. n-1]。

以[1, 2, 3]为例：找到pivot = 1（nums[1]=2 < nums[2]=3），右侧大于 2 的最小元素是 3，交换得[1, 3, 2]，后缀[2]反转后仍为[2]，结果[1, 3, 2]，与字典序一致。以[3, 2, 1]为例：无 pivot，直接整体反转得[1, 2, 3]，正确回绕到最小排列。

3.3 多语言实现

class Solution: def nextPermutation(self, nums: list[int]) -> None: """ Do not return anything, modify nums in-place instead. """ n = len(nums) i = n - 2 while i >= 0 and nums[i] >= nums[i + 1]: i -= 1 if i >= 0: j = n - 1 while nums[j] <= nums[i]: j -= 1 nums[i], nums[j] = nums[j], nums[i] l, r = i + 1, n - 1 while l < r: nums[l], nums[r] = nums[r], nums[l] l += 1 r -= 1

public class Solution { public void nextPermutation(int[] nums) { int n = nums.length; int i = n - 2; while (i >= 0 && nums[i] >= nums[i + 1]) { i--; } if (i >= 0) { int j = n - 1; while (nums[j] <= nums[i]) { j--; } swap(nums, i, j); } int l = i + 1, r = n - 1; while (l < r) { swap(nums, l++, r--); } } private void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } }

class Solution { public: void nextPermutation(vector<int>& nums) { int n = nums.size(); int i = n - 2; while (i >= 0 && nums[i] >= nums[i + 1]) { i--; } if (i >= 0) { int j = n - 1; while (nums[j] <= nums[i]) { j--; } swap(nums[i], nums[j]); } int l = i + 1, r = n - 1; while (l < r) { swap(nums[l++], nums[r--]); } } };

class Solution { /** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */ nextPermutation(nums) { const n = nums.length; let i = n - 2; while (i >= 0 && nums[i] >= nums[i + 1]) { i--; } if (i >= 0) { let j = n - 1; while (nums[j] <= nums[i]) { j--; } [nums[i], nums[j]] = [nums[j], nums[i]]; } let l = i + 1, r = n - 1; while (l < r) { [nums[l], nums[r]] = [nums[r], nums[l]]; l++; r--; } } }

public class Solution { public void NextPermutation(int[] nums) { int n = nums.Length; int i = n - 2; while (i >= 0 && nums[i] >= nums[i + 1]) { i--; } if (i >= 0) { int j = n - 1; while (nums[j] <= nums[i]) { j--; } Swap(nums, i, j); } int l = i + 1, r = n - 1; while (l < r) { Swap(nums, l++, r--); } } private void Swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } }

func nextPermutation(nums []int) { n := len(nums) i := n - 2 for i >= 0 && nums[i] >= nums[i+1] { i-- } if i >= 0 { j := n - 1 for nums[j] <= nums[i] { j-- } nums[i], nums[j] = nums[j], nums[i] } l, r := i+1, n-1 for l < r { nums[l], nums[r] = nums[r], nums[l] l++ r-- } }

class Solution { fun nextPermutation(nums: IntArray) { val n = nums.size var i = n - 2 while (i >= 0 && nums[i] >= nums[i + 1]) { i-- } if (i >= 0) { var j = n - 1 while (nums[j] <= nums[i]) { j-- } nums[i] = nums[j].also { nums[j] = nums[i] } } var l = i + 1 var r = n - 1 while (l < r) { nums[l] = nums[r].also { nums[r] = nums[l] } l++ r-- } } }

class Solution { func nextPermutation(_ nums: inout [Int]) { let n = nums.count var i = n - 2 while i >= 0 && nums[i] >= nums[i + 1] { i -= 1 } if i >= 0 { var j = n - 1 while nums[j] <= nums[i] { j -= 1 } nums.swapAt(i, j) } var l = i + 1 var r = n - 1 while l < r { nums.swapAt(l, r) l += 1 r -= 1 } } }

impl Solution { pub fn next_permutation(nums: &mut Vec<i32>) { let n = nums.len(); let mut i = n as i32 - 2; while i >= 0 && nums[i as usize] >= nums[i as usize + 1] { i -= 1; } if i >= 0 { let mut j = n - 1; while nums[j] <= nums[i as usize] { j -= 1; } nums.swap(i as usize, j); } nums[(i as usize + 1)..].reverse(); } }

3.4 复杂度分析（Time & Space Complexity）

• 时间复杂度：O(n)—— 三次线性扫描（找 pivot、找交换位、反转后缀），每步至多遍历一次数组；
• 空间复杂度：O(1)—— 完全就地修改，仅使用常数个额外变量。

这也是该题在工程上的标准答案：一次遍历定位、一次交换、一次反转，与 C++ 标准库std::next_permutation的实现思路一致。

4. 常见陷阱（Common Pitfalls）

即便掌握了贪心框架，实现时仍有三处极易出错，尤其涉及重复元素时必须格外小心。

4.1 用错误的比较方式找 Pivot

pivot 必须是最靠右的、小于其右邻居的元素，即严格满足nums[i] < nums[i+1]。如果在寻找时误用<=（写成nums[i] <= nums[i+1]才停下），算法会在含重复元素的数组上失效——它会跳过合法的 pivot 位置，导致无法得到正确的下一个排列。关键在于：递减后缀允许相等，因此必须用严格小于来判断 pivot 的终止条件。

4.2 交换了错误的元素

找到 pivot 之后，必须与其右侧所有大于 pivot 的元素中最小者交换。如果改成"从左侧起找到的第一个更大元素"进行交换，虽然排列变大了，但不是字典序上最小的增量，会跳过若干合法排列。正确做法是从最右端向左扫描，第一个满足nums[j] > nums[i]的元素就是"大于 pivot 的最小者"（因为后缀是递减的）。

4.3 忘记反转后缀

交换完成后，pivot 右侧的后缀仍是递减顺序。如果不把它反转成升序，得到的排列会比真正"下一个排列"更大。反转后缀是得到"最小的更大排列"的关键一步，与"回绕到最小排列"（整体反转）在原理上完全一致：降序是字典序最大，升序是字典序最小。

5. 总结与仓库延伸阅读

本文完整覆盖了 Next Permutation 的两种解法：O(n!·n) 的暴力枚举与 O(n) 的贪心双指针，后者通过"定位 pivot → 交换最小更大元素 → 反转后缀"三步即可就地完成，且天然兼容重复元素。需要特别记住的边界是：当数组整体降序（已是最大排列）时，直接反转整个数组回到升序（最小排列）。

若想进一步巩固排列类问题的整体体系，可继续阅读本仓库的以下资源：

• articles/permutations.md：无重复元素全排列的生成与回溯框架；
• articles/permutations-ii.md：含重复元素时的去重剪枝技巧；
• articles/permutation-string.md：排列在子串匹配（滑动窗口）中的应用；
• java/0060-permutation-sequence.java：第 k 个排列的数学解法，其注释展示了与本题暴力法的直接关联；
• articles/next-permutation.md：本篇的原始题解文档，含全部多语言实现。

掌握了"下一个排列"这一原子操作，你就可以进一步解决"第 k 个排列"、"全排列"、"排列字符串匹配"等一系列字典序与排列问题。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode