vvrf / DSA.log

问题拆解

把数组原地改成它在字典序里的下一个排列；如果已经是最大的（整体降序），就回到最小的（整体升序）。朴素思路是生成全部排列排好序再找后继，O(n!) 想都不用想——必须直接从当前排列推出下一个。

关键是想清楚“下一个”对数字意味着什么。把排列看成一个数，下一个排列就是比它大的数里最小的那个。要变大，必须把某个位置换成更大的数字；要增量最小，这个位置应该尽量靠右，换上去的数应该尽量小，换完之后右边的后缀应该排成最小（升序）。

从右往左，降序的后缀已经是“这些数字能摆出的最大值”，动它内部没有用；第一个打破降序的位置 i（即 nums[i] < nums[i+1]）就是必须动手的地方。

找升序对、交换、反转后缀

顺着上面的观察，算法只有四步：从右找第一个满足 nums[i] < nums[i+1] 的 i；再从右找第一个大于 nums[i] 的数 nums[j]；交换两者；把 i 之后的后缀整段反转。

public void nextPermutation(int[] nums) {
    int n = nums.length;
    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--; // 后缀降序，从右数第一个大于 nums[i] 的就是“刚好大一点”的
        }
        int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
    }
    // 反转后缀，把它从最大排列变成最小排列
    for (int l = i + 1, r = n - 1; l < r; l++, r--) {
        int tmp = nums[l]; nums[l] = nums[r]; nums[r] = tmp;
    }
}

def nextPermutation(nums: list[int]) -> None:
    n = len(nums)
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1  # 从右找第一个升序对

    if i >= 0:
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1  # 后缀降序，从右数第一个大于 nums[i] 的就是“刚好大一点”的
        nums[i], nums[j] = nums[j], nums[i]

    # 反转后缀，把它从最大排列变成最小排列
    nums[i + 1:] = nums[i + 1:][::-1]

func nextPermutation(nums []int) {
    n := len(nums)
    i := n - 2
    for i >= 0 && nums[i] >= nums[i+1] {
        i-- // 从右找第一个升序对
    }
    if i >= 0 {
        j := n - 1
        for nums[j] <= nums[i] {
            j-- // 后缀降序，从右数第一个大于 nums[i] 的就是“刚好大一点”的
        }
        nums[i], nums[j] = nums[j], nums[i]
    }
    slices.Reverse(nums[i+1:]) // 反转后缀，把它从最大排列变成最小排列
}

pub fn next_permutation(nums: &mut Vec<i32>) {
    let n = nums.len();
    if n < 2 {
        return;
    }
    let mut i = n - 1;
    while i > 0 && nums[i - 1] >= nums[i] {
        i -= 1; // i-1 与 i 构成从右数第一个升序对
    }
    if i > 0 {
        let mut j = n - 1;
        while nums[j] <= nums[i - 1] {
            j -= 1; // 后缀降序，从右数第一个大于 nums[i-1] 的就是“刚好大一点”的
        }
        nums.swap(i - 1, j);
    }
    nums[i..].reverse(); // 反转后缀，把它从最大排列变成最小排列
}

为什么这就是“恰好下一个”？三步各自对应一条最小化原则。改动位选在最靠右的可改位置——i 右边是降序后缀，内部怎么排都到顶了，不动 i 就不可能变大。换上的数选后缀里大于 nums[i] 的最小者——后缀降序，从右往左第一个大于 nums[i] 的正是它；换小了不构成“变大”，换大了增量就不是最小。交换后后缀仍保持降序（nums[j] 的左邻不小于它、右邻不大于 nums[i]），所以整段反转就得到升序，即这批数字的最小排列。三处都取到下界，结果就是严格的后继。

易错点集中在等号上：找 i 时条件是 nums[i] >= nums[i+1] 继续左移，相等不算升序对，否则 [1, 5, 1] 这类含重复元素的用例会选错位置；找 j 时 nums[j] <= nums[i] 继续左移，必须严格大于才交换。整体降序时 i 走到 -1，跳过交换、只做反转，恰好回到最小排列，无需特判。

复杂度

指标	复杂度	原因
时间	`O(n)`	两次从右扫描加一次反转，各至多一遍
空间	`O(1)`	原地交换与反转，只用常数下标

可以迁移的模式

“下一个更大且增量最小”类问题，从低位（右侧）找第一个可改动点，是字典序的通用直觉；
降序段等于“已到达最大”，升序段等于“还有上升空间”——单调性本身就是信息；
交换后利用“后缀仍降序”的不变量，用 O(n) 反转替代 O(n log n) 排序。

这套四步操作就是 C++ 标准库 std::next_permutation 的实现，值得整段背下来。