LeetCode 31. 下一个排列
题目描述
题意分析
在不改变元素及其出现次数的前提下，调整
nums的顺序，得到字典序中紧邻当前排列的下一个排列。字典序从左到右比较，第一对不相等的元素决定两个排列的大小。答案既要比当前排列大，又要是所有更大排列中最小的一个；如果当前排列已经最大，则改成升序排列。数组允许有重复元素，必须原地修改，额外空间只能为常数。
解法：寻找可增大位置 + 反转后缀
核心思路
[!blue]
字典序由最靠左的差异决定，所以要让排列只增大一点，首先应尽量保留左侧前缀，把需要增大的位置放得越靠右越好。
从右向左寻找第一个满足
nums[i] < nums[i + 1]的位置。此时[i + 1, n - 1]一定非递增，已经是这些后缀元素能组成的最大排列：只调整后缀不可能得到更大的结果。因此必须改变i或更左的位置，而改变i能保留最长的前缀。位置确定后，
nums[i]也要尽量少增大。后缀非递增，从末尾向左找到的第一个严格大于nums[i]的元素，就是可替换它的最小值。把两者交换，便确定了最小的更大前缀。最后让剩余后缀尽量小，也就是升序排列。交换后的后缀仍然非递增：交换位置左边的元素不小于被取走的值，右边的元素都不大于原来的
nums[i]，把原值放到这里不会破坏顺序。因此直接反转后缀即可，无需重新排序。如果找不到这样的
i，整个数组都非递增，已经不存在更大排列。此时反转整个数组，得到题目要求的最小排列。
解题步骤
- 令
i = n - 2，只要nums[i] >= nums[i + 1]就继续左移，找到最靠右的可增大位置。- 若
i >= 0，令j = n - 1，向左跳过所有nums[j] <= nums[i]的元素，再交换nums[i]与nums[j]。- 用左右指针反转
[i + 1, n - 1]。若i = -1，反转范围自然变成整个数组；只有一个元素时无需交换。
代码实现
class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
// 跳过已经最大的非递增后缀，找到最靠右的可增大位置。
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
// 从后缀末尾找到最小的严格更大值。
while (nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
// 把非递增后缀反转成最小排列；没有可提升位置时也要反转整个数组。
reverse(nums, i + 1, nums.length - 1);
}
private void reverse(int[] nums, int left, int right) {
while (left < right) {
swap(nums, left, right);
left++;
right--;
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
func nextPermutation(nums []int) {
i := len(nums) - 2
// 跳过已经最大的非递增后缀，找到最靠右的可增大位置。
for i >= 0 && nums[i] >= nums[i+1] {
i--
}
if i >= 0 {
j := len(nums) - 1
// 从后缀末尾找到最小的严格更大值。
for nums[j] <= nums[i] {
j--
}
nums[i], nums[j] = nums[j], nums[i]
}
// 把非递增后缀反转成最小排列；没有可提升位置时也要反转整个数组。
for left, right := i+1, len(nums)-1; left < right; left, right = left+1, right-1 {
nums[left], nums[right] = nums[right], nums[left]
}
}
复杂度分析
- 时间复杂度：$O(n)$，两次查找和一次反转各自最多遍历数组一遍，顺序执行的扫描次数相加仍为线性。
- 空间复杂度：$O(1)$，在原数组上修改。
关键点总结
[!green]
- 保留最长前缀、让拐点最小幅度增大、让后缀最小，三步共同保证得到紧邻的下一个排列。
- 非递增后缀既决定了拐点，也让替换值可以从右查找、剩余部分可以直接反转。
- 等值元素不能使排列变大，寻找拐点与替换值时都必须体现严格增大的要求。
易错点总结
[!yellow]
- 查找拐点时漏掉等号，重复元素会导致错误。
- 交换时使用大于等于而非严格大于，排列可能没有变大。
- 找不到拐点时仍尝试交换，会访问负下标。
- 反转起点应为
i + 1，且无论是否找到拐点都要执行。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 556. 下一个更大元素 III | 中等 | 把整数各位视为排列后，寻找更大且最接近的值，复用找枢轴和整理后缀。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！