Leetcode Next Permutation：字典序下一個排列算法

問題描述

給定整數數組，原地修改為字典序下一個排列。若不存在（已是最大排列），重置為最小排列（升序）。要求 O(1) 額外空間。

算法規律

1. 從右向左找第一個 a[i] < a[i+1] 的位置 i（逆序對邊界）
2. 從右向左找第一個 a[j] > a[i] 的位置 j
3. 交換 a[i] 和 a[j]
4. 反轉 i+1 到末尾的子數組（使其升序，即最小）

參考代碼（C++）

class Solution {
public:
    void nextPermutation(vector& nums) {
        int n = nums.size(), i = n - 2;
        // 1. 找逆序對邊界
        while (i >= 0 && nums[i] >= nums[i+1]) i--;
        if (i >= 0) {
            // 2. 找右側比 nums[i] 大的最小元素（實際是從右找第一個大的）
            int j = n - 1;
            while (nums[j] <= nums[i]) j--;
            swap(nums[i], nums[j]);
        }
        // 3. 反轉後綴
        reverse(nums.begin() + i + 1, nums.end());
    }
};

示例演示

1 2 3 → i=1 (2<3), j=2 (3>2), swap→1 3 2, reverse 後綴(單元素)→1 3 2
3 2 1 → i=-1 (全降序), 直接 reverse→1 2 3
1 1 5 → i=1 (1<5), j=2 (5>1), swap→1 5 1, reverse 後綴→1 5 1

複雜度

• 時間：O(n)，單次掃描 + 反轉
• 空間：O(1)，原地修改

關鍵點

1. 「字典序下一個」=「盡可能靠右的微小增大」
2. 後綴必須是降序（否則能在後綴內部找到更小的增大）
3. reverse 等價於對降序後綴排序升序