.jpg)
931 字
5 分钟
下一个排列
.jpg)
题目描述
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如，
arr = [1,2,3]，以下这些都可以视作arr的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
- 例如，
arr = [1,2,3]的下一个排列是[1,3,2]。 - 类似地，
arr = [2,3,1]的下一个排列是[3,1,2]。 - 而
arr = [3,2,1]的下一个排列是[1,2,3]，因为[3,2,1]不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
解题思路
- 逆向扫描定位：
- 从右向左扫描，找到第一个非递增位置
i（满足nums[i] < nums[i+1]） - 此时
i右侧的元素构成最大降序序列
- 从右向左扫描，找到第一个非递增位置
- 交换关键元素：
- 在
i右侧找到最小大于nums[i]的元素nums[j] - 交换
nums[i]和nums[j]
- 在
- 右侧序列重置：
- 将
i+1开始的右侧序列逆转为升序 - 确保新排列是恰好大于原排列的最小值
- 将
- 边界处理：
- 若整个序列降序，则返回最小排列（升序）
关键洞察
- 字典序特性：
- 下一个排列应是恰好大于当前排列的最小字典序排列
- 无需遍历所有排列组合
- 递减序列性质：
- 从右开始的递减序列已达最大值
- 需要左侧首个较小值触发变化
- 交换原则：
- 选择右侧最小较大值交换，确保变化最小
- 右侧重置必要性：
- 交换后右侧仍保持最大降序
- 逆转为升序转化为最小可能值
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(n)：三次线性扫描（查找、交换、反转） |
| 空间复杂度 | O(1)：原地操作，仅需常数额外空间 |
代码实现
const nextPermutation = (nums) => { const n = nums.length; let i = n - 2;
// 1. 从右向左找第一个非递增位置 while (i >= 0 && nums[i] >= nums[i + 1]) { i--; }
// 2. 如果找到可交换位置 if (i >= 0) { let j = n - 1; // 在右侧找最小大于nums[i]的值 while (j > i && nums[j] <= nums[i]) { j--; } // 交换关键元素 [nums[i], nums[j]] = [nums[j], nums[i]]; }
// 3. 反转右侧序列为升序 let left = i + 1; let right = n - 1; while (left < right) { [nums[left], nums[right]] = [nums[right], nums[left]]; left++; right--; }};
// 测试用例const test = [1, 2, 3];nextPermutation(test);console.log(test); // [1,3,2]
const test2 = [3, 2, 1];nextPermutation(test2);console.log(test2); // [1,2,3]
const test3 = [1, 5, 8, 4, 7, 6, 5, 3, 1];nextPermutation(test3);console.log(test3); // [1,5,8,5,1,3,4,6,7]算法执行流程
输入: [1,5,8,4,7,6,5,3,1]
步骤:1. 从右扫描: - 1<3? 否 → 3<5? 否 → 5<6? 否 → 6<7? 否 → 7<4? 是 → i=3 (值4)2. 在右侧[7,6,5,3,1]找最小大于4的值: 53. 交换4和5 → [1,5,8,5,7,6,4,3,1]4. 反转右侧[7,6,4,3,1] → [1,3,4,6,7]结果: [1,5,8,5,1,3,4,6,7]实际应用场景
- 密码破解：按字典序生成所有排列尝试`
- 组合优化：旅行商问题邻域搜索`
- 字典系统：单词按字母顺序生成下一个排列`
- 游戏解谜：数字谜题的状态转移`