下一个排列 图解题解

这道题到底在问什么

nums

[1,2,7,4,3,1]

输出

[1,3,1,2,4,7]

先想最直接的笨办法

暴力是把所有排列都列出来、排好序、找到当前这个的下一个。n 个数有 n 的阶乘种排列，光是 10 个数就三百多万种，直接超时。（动画第 3 步）

最优解：一步一步想明白

1. 3暴力是把所有排列都列出来、排好序、找到当前这个的下一个。n 个数有 n 的阶乘种排列，光是 10 个数就三百多万种，直接超时。
2. 4高位不动、只动靠右的位，增幅才最小。所以我们从右往左找：第一个「还能往上抬一点」的位置。
3. 5右段 7＞4＞3＞1 一路递减，到 2 才被打破从最右边的 1 开始往左看。1 比 3 小？不，1 在 3 右边、比它小，继续。我们要找的是「左边比右边小」的那个台阶。
4. 61 ＜ 3 ＜ 4 ＜ 7：从右看一路是上坡，没法动7、4、3、1 这一段从左到右是递减的，它本身已经是最大排法，动它只会变小。所以越过它，继续往左。
5. 72 ＜ 7：终于找到能抬高的位置，i=1走到下标 1，值是 2，它右边的 7 比它大。这就是下降点 i。我们要把这一位的 2 换成右边一个稍大的数。
6. 8在 i 右边的后缀里，从右往左找第一个 ＞ 2 的数现在盯住 i 右边这段。从最右的 1 开始往左找：1 比 2 大吗？不大，跳过。
7. 91 不行、3 可以：3 是右段里＞2 的最小数再往左是 3，比 2 大，停。因为右段是递减的，从右数第一个比 2 大的，正好就是「比 2 大但大得最少」的那个，它就是要换上高位的数。
8. 10高位 2 换成 3：前缀刚好抬高了一格交换 i 和 j：2 和 3 互换。注意看下标 1 变成了 3、下标 4 变成了 2。前缀 1,3 已经比原来大，这一步保证了「确实变大」。
9. 11换完之后，i 右边 7,4,2,1 依然从大到小排换完后，i 右边的 7,4,2,1 还是从大到小。前缀已经抬高了，尾巴就该取「最小」才整体最接近——但现在它是最大，得把它翻成最小。
10. 12l=2、r=5：交换两端 7 和 1用左右双指针反转后缀。l 在 2、r 在 5，交换两端：7 和 1 互换。后缀正从「最大」一步步翻成「最小」。
11. 13l=3、r=4：交换 4 和 2，指针相遇即结束l 走到 3、r 走到 4，交换 4 和 2。再走一步两指针就相遇，反转结束。后缀变成 1,2,4,7，是这个前缀下最小的尾巴。
12. 14前缀抬一格 + 尾巴取最小 = 刚好大一点点结果出来了：[1,3,1,2,4,7]。高位被尽量靠右地抬高一格、尾巴换成升序最小，这就是字典序里紧挨着的下一个排列。
13. 17一句话本质：把尽量靠右的高位抬高最小的一格，再把它后面的尾巴翻成升序最小，整体就刚好大一点点。
14. 19整段递减，找不到下降点 i，i 退到 -1[3,2,1] 已经是最大排列。从右往左每一步都是「左大于右」，i 一直左移到越界。这时不交换，直接进第三步反转整段。
15. 20i=-1，反转 0 到末尾，回到升序最小因为 i+1 等于 0，第三步反转的是整个数组，[3,2,1] 翻成 [1,2,3]，正好是字典序最小的排列。这就是「最大变最小」的兜底分支。
16. 24这套「找降点-换大数-翻后缀」是排列类的原子操作。会了它，再去看全排列 lc46 的回溯、以及康托展开求第 k 个排列，会顺很多。点开数组专题或问问小欧 AI 私教继续练。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def nextPermutation(self, nums):
        n = len(nums)
        i = n - 2
        # 1. 从右往左找下降点 i
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        # 2. 若存在 i，右段找刚好大于 nums[i] 的 j 并交换
        if i >= 0:
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        # 3. 反转 i 之后的后缀（递减翻成递增）
        l, r = i + 1, n - 1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size(), i = n - 2;
        // 1. 从右往左找下降点 i
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        // 2. 右段找刚好大于 nums[i] 的 j 并交换
        if (i >= 0) {
            int j = n - 1;
            while (nums[j] <= nums[i]) j--;
            swap(nums[i], nums[j]);
        }
        // 3. 反转 i 之后的后缀
        reverse(nums.begin() + i + 1, nums.end());
    }
};

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length, i = n - 2;
        // 1. 从右往左找下降点 i
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        // 2. 右段找刚好大于 nums[i] 的 j 并交换
        if (i >= 0) {
            int j = n - 1;
            while (nums[j] <= nums[i]) j--;
            int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
        }
        // 3. 反转 i 之后的后缀
        for (int l = i + 1, r = n - 1; l < r; l++, r--) {
            int t = nums[l]; nums[l] = nums[r]; nums[r] = t;
        }
    }
}

# 字典序「下一个排列」三步骨架，括号处自己补：
# 第 1 步：从右往左找下降点 i
i = n - 2
while i >= 0 and nums[i] ___ nums[i+1]:  # 填 >= 
    i -= 1
# 第 2 步：i 存在则在右段找最小的更大数 j 交换
if i >= 0:
    j = n - 1
    while nums[j] ___ nums[i]:  # 填 <= 
        j -= 1
    swap(i, j)
# 第 3 步：无论 i 是否存在，都反转 i+1..末尾
reverse(nums, ___ , n - 1)   # 起点填 i + 1

// 三步骨架：__ 处自己补判据
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]);
}
reverse(nums.begin() + /*__*/ i + 1, nums.end());

// 三步骨架：__ 处自己补判据
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--;
    int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
}
for (int l = i + 1, r = n - 1; l < r; l++, r--) {
    int t = nums[l]; nums[l] = nums[r]; nums[r] = t;
}

复杂度

面试官可能追问