Java版LeetCode热题100之下一个排列：深入解析与实战应用

Java版LeetCode热题100之下一个排列：深入解析与实战应用

本文目标：全面、系统地讲解 LeetCode 第31题「下一个排列」（Next Permutation），从题目理解、算法推导、代码实现到面试技巧和实际应用场景，帮助你真正掌握这道经典且高频的算法题。

一、原题回顾

题目描述

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3]，以下这些都可以视作arr的排列：
[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。

整数数组的下一个排列是指其整数的下一个字典序更大的排列。

更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。

特殊情况：如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

示例

示例 1：

输入：nums = [1,2,3] 输出：[1,3,2]

示例 2：

输入：nums = [3,2,1] 输出：[1,2,3]

示例 3：

输入：nums = [1,1,5] 输出：[1,5,1]

约束条件

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100
• 必须原地修改，只允许使用额外常数空间。

二、原题分析

核心概念：字典序（Lexicographical Order）

字典序类似于英文词典的排序方式：

• 比较两个序列时，从左到右逐位比较；
• 第一个不同的位置决定大小；
• 若一个序列是另一个的前缀，则短者更小。

例如：

• [1,2,3] < [1,3,2]（因为第2位 2 < 3）
• [2,1,3] < [2,3,1]（因为第2位 1 < 3）
• [3,2,1]是最大排列，其下一个是[1,2,3]（循环回最小）

问题本质

给定一个排列，找到紧邻其后的字典序更大的排列。若已是最大，则返回最小排列。

这不仅是理论问题，更是组合数学与算法设计的经典交汇点。

难点剖析

1. 如何高效找到“下一个”？
   不能生成所有排列再找（时间爆炸）。

2. 如何保证“刚好更大”？
   不能随便交换，必须使变化幅度最小。

3. 如何原地操作？
   不能使用额外数组存储中间结果。

4. 边界情况处理
   如全降序（最大排列）、含重复元素等。

三、答案构思

直观尝试（错误思路）

• 从右往左找第一个可增大的位置，直接+1？
  ❌ 错误：数字不是连续的，且可能超出范围。

• 找到最右边能交换的位置，交换后排序？
  ❌ 可能跳过中间排列，如[1,2,3] → [1,3,2]正确，但[2,3,1] → [3,2,1]错误（应为[3,1,2]）。

正确思路：贪心 + 局部优化

要使新排列刚好大于原排列，需满足：

1. 改动尽可能靠右（高位不变，低位调整）；
2. 改动幅度尽可能小；
3. 改动后右侧部分应最小化（升序）。

关键观察

• 从右往左，找到第一个下降的位置i，即nums[i] < nums[i+1]。

  • 说明[i+1, n)是严格非升序（降序或相等）。
  • 这是我们能“增大”的最右位置。

• 在[i+1, n)中，找到最小的比nums[i]大的数nums[j]。

  • 因为右侧是降序，从右往左找第一个> nums[i]即可。

• 交换nums[i]和nums[j]。

  • 此时[i+1, n)仍是降序（因为nums[j]是最小的大于nums[i]的数）。

• 将[i+1, n)反转为升序，使其成为最小可能。

✅ 这样既保证了新排列 > 原排列，又使增量最小。

特殊情况处理

• 若找不到i（即整个数组非升序），说明已是最大排列，直接反转整个数组得到最小排列。

四、完整答案（Java实现）

classSolution{publicvoidnextPermutation(int[]nums){intn=nums.length;// Step 1: 从右往左找第一个 nums[i] < nums[i+1]inti=n-2;while(i>=0&&nums[i]>=nums[i+1]){i--;}// Step 2: 如果找到，再从右往左找第一个 nums[j] > nums[i]if(i>=0){intj=n-1;while(j>=0&&nums[j]<=nums[i]){j--;}// 交换 nums[i] 和 nums[j]swap(nums,i,j);}// Step 3: 反转 [i+1, n) 区间reverse(nums,i+1);}// 辅助函数：交换两个元素privatevoidswap(int[]nums,inti,intj){inttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}// 辅助函数：从 start 开始反转数组privatevoidreverse(int[]nums,intstart){intleft=start;intright=nums.length-1;while(left<right){swap(nums,left,right);left++;right--;}}}

代码执行流程示例

以nums = [4,5,2,6,3,1]为例：

1. 找 i：

   • 从右：1→3→6→2，发现2 < 6，所以i = 2（值为2）

2. 找 j：

   • 从右找第一个> 2：1→3（3>2），所以j = 4（值为3）

3. 交换：

   • [4,5,2,6,3,1] → [4,5,3,6,2,1]

4. 反转 [i+1, n)：

   • 反转[6,2,1]→[1,2,6]
   • 最终：[4,5,3,1,2,6]

✅ 正确！这是字典序中紧接[4,5,2,6,3,1]的下一个排列。

五、代码分析

模块化设计

• nextPermutation：主逻辑，三步走
• swap：原子交换操作
• reverse：区间反转，用于将降序变升序

关键细节

1. 为什么nums[i] >= nums[i+1]用>=？
   处理重复元素。例如[1,1,5]，i=1（第二个1），因为1 < 5。

2. 为什么找j时用nums[j] <= nums[i]？
   确保找到的是严格大于nums[i]的最小值。

3. 为什么反转而不是排序？
   因为[i+1, n)在交换前是非升序，交换后仍保持非升序（证明见下文），所以反转即可得升序，O(n) 比排序 O(n log n) 更优。

正确性证明（简要）

• 交换后[i+1, n)仍为非升序：
  假设原[i+1, n)为降序，nums[j]是其中最小的大于nums[i]的数。
  交换后，nums[i]变为nums[j]，而nums[j]变为原nums[i]。
  由于nums[j-1] >= nums[j] > nums[i] >= nums[j+1]，所以新nums[j] = 原 nums[i] <= nums[j-1]，且>= nums[j+1]，整体仍非升序。

• 反转后为最小可能：
  升序是给定元素集合的最小字典序排列。

六、时间复杂度与空间复杂度分析

详细说明

• 时间复杂度 O(n)：

  • 第一次 while 循环：最多遍历 n-1 次
  • 第二次 while 循环：最多遍历 n-1 次
  • reverse 操作：最多 n/2 次交换
  • 总计：3n/2 ≈ O(n)

• 空间复杂度 O(1)：

  • 仅使用常数个变量（i, j, left, right, temp）
  • 无递归、无额外数组

✅ 完美满足题目“原地修改 + 常数空间”要求。

七、常见问题解答（FAQ）

Q1：为什么不能直接对[i+1, n)排序？

A：可以，但没必要。因为该区间在交换前后都是非升序，反转即可得到升序，时间复杂度 O(k)（k 为区间长度），而排序需 O(k log k)。在算法竞赛和面试中，最优解应追求常数因子最小。

Q2：如果数组中有重复元素，算法还正确吗？

A：完全正确。
例如nums = [1,1,5]：

• i = 1（因为1 < 5）
• j = 2（5 > 1）
• 交换 →[1,5,1]
• 反转[1]→ 不变
• 结果[1,5,1]正确。

再如nums = [2,3,1,3,3]：

• i = 2（1 < 3）
• j = 4（最后一个3 > 1）
• 交换 →[2,3,3,3,1]
• 反转[3,1]→[1,3]
• 结果[2,3,3,1,3]是下一个排列。

Q3：这个算法和 C++ 的next_permutation一样吗？

A：完全一致！
C++ STL 中的std::next_permutation正是采用此算法，时间复杂度 O(n)，支持重复元素。

Q4：如何验证结果正确？

A：可通过以下方式：

1. 手动列出小规模排列（如 n≤4）
2. 使用 Python 的itertools.permutations生成所有排列并排序
3. 对比算法输出是否匹配

例如 Python 验证：

fromitertoolsimportpermutations arr=[1,2,3]perms=sorted(set(permutations(arr)))idx=perms.index(tuple(arr))next_perm=perms[(idx+1)%len(perms)]print(next_perm)# (1, 3, 2)

八、优化思路

1. 减少函数调用开销（微优化）

将swap和reverse内联到主函数中，减少方法调用栈开销（在极端性能场景下考虑）：

publicvoidnextPermutation(int[]nums){intn=nums.length;inti=n-2;while(i>=0&&nums[i]>=nums[i+1])i--;if(i>=0){intj=n-1;while(nums[j]<=nums[i])j--;// 内联交换inttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}// 内联反转intleft=i+1,right=n-1;while(left<right){inttemp=nums[left];nums[left]=nums[right];nums[right]=temp;left++;right--;}}

💡 实际开发中，可读性优先，除非性能瓶颈明确。

2. 提前终止（无实质收益）

无法提前终止，因为必须完成三步才能保证正确性。

3. 使用位运算交换（不推荐）

nums[i]^=nums[j];nums[j]^=nums[i];nums[i]^=nums[j];

• 缺点：当i == j时，结果为0（错误！）
• 结论：安全起见，使用临时变量。

九、数据结构与算法基础知识点回顾

1. 字典序（Lexicographical Order）

• 定义：序列 A < B，当存在 k 使得 A[0…k-1] = B[0…k-1] 且 A[k] < B[k]
• 应用：字符串排序、排列生成、版本号比较

2. 贪心策略（Greedy Algorithm）

• 局部最优 → 全局最优
• 本题中：“改动最右 + 幅度最小” 是贪心选择

3. 双指针技巧

• reverse函数使用左右双指针
• 时间 O(n)，空间 O(1)

4. 原地算法（In-place Algorithm）

• 不使用额外空间（或 O(1)）
• 常见于排序、数组变换类问题

5. 排列生成算法

• 字典序法：本题所用
• 递归回溯法：生成所有排列
• Johnson-Trotter 算法：相邻交换生成

💡 本题是字典序生成法的核心步骤。

十、面试官提问环节（模拟）

Q：你能手动画出[1,3,2]的下一个排列吗？

答：

1. 从右找：2→3，发现1 < 3，所以i=0
2. 从右找第一个>1：2>1，所以j=2
3. 交换：[2,3,1]
4. 反转[3,1]→[1,3]
5. 结果：[2,1,3]

✅ 正确。

Q：为什么找j时要从右往左？

答：因为[i+1, n)是非升序，从右往左找第一个> nums[i]能保证找到的是最小的满足条件的数，从而使交换后的增量最小。

例如[1,2,5,4,3]，i=1（值为2），右侧[5,4,3]。
从右找：3→4→5，第一个>2是3？不对！
实际上，5>2, 4>2, 3>2，但我们要最小的大于2的数，即3。
但由于数组是降序，最右边的大于2的数就是最小的，所以从右找第一个即可。

Q：如果要求上一个排列（prev permutation）怎么做？

答：对称操作：

1. 从右找第一个nums[i] > nums[i+1]
2. 从右找第一个nums[j] < nums[i]
3. 交换
4. 反转[i+1, n)

Q：这个算法能处理空数组或单元素吗？

答：可以。

• 空数组：n=0，i = -2，跳过交换，reverse( -1 )不执行（left=-1, right=-1，while 不成立）
• 单元素：n=1，i = -1，同上，结果不变（也是最小排列）

十一、这道算法题在实际开发中的应用

1. 组合优化与搜索

在回溯算法中，若需按字典序生成所有排列，可避免递归，直接迭代调用nextPermutation，节省栈空间。

// 生成所有排列（迭代版）int[]nums={1,2,3};do{System.out.println(Arrays.toString(nums));}while(hasNextPermutation(nums));// 自定义判断

2. 密码学与穷举攻击

在暴力破解中，按字典序生成密码组合，确保不遗漏且有序。

3. 调度与资源分配

任务调度中，若需尝试所有任务顺序，按字典序生成可保证公平性和可预测性。

4. 游戏开发：关卡生成

Roguelike 游戏中，房间布局的排列可按字典序生成，确保每次游戏体验不同但可控。

5. 测试用例生成

自动化测试中，生成所有参数组合的排列，验证系统鲁棒性。

6. 数学计算库

如 Python 的itertools、C++ 的<algorithm>，底层均使用此类高效算法。

十二、相关题目推荐

💡 建议：掌握本题后，尝试解决556. 下一个更大元素 III，它是本题的变形（输入为整数）。

十三、总结与延伸

核心思想总结

1. 字典序的下一个排列 = 最小的增量调整
2. 三步法：
   • 找最右可增位置i
   • 找最小可换值j
   • 反转右侧为升序
3. 贪心策略：局部最优（改动最右、幅度最小） → 全局最优

延伸思考

Q：能否用递归实现？

A：可以，但效率低。递归更适合生成所有排列，而非单次求下一个。

Q：如果要求第 k 个下一个排列？

A：重复调用 k 次，或结合数学方法（如阶乘数系统）直接计算。

Q：如何判断两个排列是否相邻？

A：计算它们的字典序 rank，差值为1即相邻。但 rank 计算本身复杂。

面试建议

• 务必手写代码，注意边界（如i = -1）
• 解释每一步的动机，展示算法思维
• 提及 C++ STL 的实现，体现知识广度
• 讨论重复元素处理，展示严谨性

结语：
“下一个排列”看似简单，却融合了字典序、贪心、双指针、原地操作等多重算法思想。
它不仅是 LeetCode 热题，更是程序员基本功的试金石。
掌握它，你便掌握了高效生成排列的钥匙，也为更复杂的组合问题打下坚实基础。