下一个排列
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
给你一个整数数组 nums，找出 nums 的下一个排列。
必须原地修改，只允许使用额外常数空间。
示例 1
示例 2
示例 3
模拟答题者思考
1. 我先想暴力：生成所有排列、排序、找当前排列的下一个——能过但 O(n×n!)，完全不可接受。
2. 重复在哪里？字典序的「下一个」有规律：从右往左看，若后缀是严格降序（如 [3,2,1]），说明没有更大的了，只能回到最小排列。
3. 关键观察：找第一个 nums[i] < nums[i+1]，说明 i 右侧是降序后缀；要让整体字典序变大，必须增大 nums[i]，且增幅要尽可能小。
4. 因此在后缀中找刚好比 nums[i] 大的最小元素 nums[j]，交换 nums[i] 与 nums[j]；交换后 i+1 右侧仍是降序，再反转后缀得到升序，即「下一个排列」。
5. 若找不到这样的 i，说明整个数组降序，直接反转全数组即可得到最小排列；全程原地 O(n) 时间、O(1) 空间。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
i | int | 定义：从右向左第一个满足 nums[i] < nums[i+1] 的下标，即「后缀升序」被打破的位置维护：若找不到则当前已是最大排列，需整体反转 更新：从 n-2 向左扫描，找到第一个「比右边邻居小」的元素 |
j | int | 定义：在 i 右侧后缀中，从右向左第一个满足 nums[j] > nums[i] 的下标维护：保证交换后 nums[i] 位置换成「后缀中刚好比它大的最小值」更新：从 n-1 向左扫描至 i+1，找到第一个大于 nums[i] 的元素 |
left / right | int | 定义：交换后待反转后缀 nums[i+1..n-1] 的双指针边界维护：后缀经交换后仍降序，反转后变为升序，得到「刚好大一点的」最小后缀 更新： left = i+1，right = n-1，双指针向中间交换直至 left >= right |
落码步骤
1. 令 n = len(nums)，从 i = n-2 向左找第一个 nums[i] < nums[i+1]
2. 若找不到 i（i < 0）：整个数组降序，反转 nums[0..n-1] 后返回
3. 从 j = n-1 向左找第一个 nums[j] > nums[i]
4. 交换 nums[i] 与 nums[j]
5. 双指针反转后缀 nums[i+1..n-1]（left = i+1，right = n-1，交换并向中间移动）
代码实现
class Solution:
def nextPermutation(self, nums: list[int]) -> None:
n = len(nums)
# 1. 从右向左找第一个「升序对」的左端 i
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
# 2. 在后缀中找刚好比 nums[i] 大的元素 j
j = n - 1
while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
# 3. 反转 i+1 到末尾（若 i<0 则反转整个数组）
left, right = i + 1, n - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n = nums.size();
// 1. 从右向左找第一个「升序对」的左端 i
int i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
// 2. 在后缀中找刚好比 nums[i] 大的元素 j
int j = n - 1;
while (nums[j] <= nums[i]) {
j--;
}
swap(nums[i], nums[j]);
}
// 3. 反转 i+1 到末尾（若 i<0 则反转整个数组）
reverse(nums.begin() + i + 1, nums.end());
}
};
// 时间 O(n)，空间 O(1)复杂度分析
O(n)
O(1)
常见坑
找 i 的条件是 nums[i] < nums[i+1]（严格小于），不是 <=；相等时不能停，否则重复元素会选错下一个排列。
找 j 时同样用严格大于 nums[i]；交换后必须反转后缀，不能只交换就结束——后缀仍是降序，不反转得不到最小合法后缀。
当 i < 0（已是最大排列）时，跳过交换步骤，直接反转整个数组；忘记这一步会返回原数组而非最小排列。
必测边界 Case
nums = [1] → [1]（i = -1，反转自身不变）
nums = [3,2,1] → [1,2,3]（找不到 i，整体反转）
nums = [1,1,5] → [1,5,1]（i=1, j=2，交换后反转后缀）