LeetCode 題解：Next Permutation 算法詳解與實現

問題描述

實現 nextPermutation 函數，將給定數字序列重新排列為字典序中下一個更大的排列。若不存在更大的排列，則重新排列為最小的排列（即升序排列）。要求原地修改，不分配額外記憶體。

範例：

• 1,2,3 → 1,3,2
• 3,2,1 → 1,2,3
• 1,1,5 → 1,5,1

解題思路

核心思想是從序列尾部向前尋找第一對相鄰遞增元素（即 nums[i] < nums[i+1]）。若找到，則從尾部再找第一個大於 nums[i] 的元素 nums[j]，交換兩者，最後將 i+1 到末尾的子序列反轉。若整個序列遞減，則直接反轉整個序列。

這正是 C++ STL 中 next_permutation 的實現原理。

算法步驟

1. 從右向左遍歷，找到第一個滿足 nums[i] < nums[i+1] 的索引 i。
2. 若找到，再從右向左找到第一個大於 nums[i] 的索引 j。
3. 交換 nums[i] 和 nums[j]。
4. 反轉 i+1 到末尾的子數組。
5. 若未找到這樣的 i，說明序列已是最大字典序，直接反轉整個數組得到最小字典序。

代碼實現 (C++)

class Solution {
public:
    void nextPermutation(vector& nums) {
        int n = nums.size();
        int i = n - 2;
        // 步驟1：找到第一個遞增對
        while (i >= 0 && nums[i] >= nums[i+1]) i--;
        if (i >= 0) {
            int j = n - 1;
            // 步驟2：找到第一個大於 nums[i] 的元素
            while (j >= 0 && nums[j] <= nums[i]) j--;
            swap(nums[i], nums[j]);
        }
        // 步驟3：反轉後綴
        reverse(nums.begin() + i + 1, nums.end());
    }
};

複雜度分析

• 時間複雜度：O(n)，其中 n 為數組長度。我們最多遍歷數組兩次。
• 空間複雜度：O(1)，原地修改，僅使用常數額外空間。

總結

Next Permutation 是經典的字典序排列生成算法，掌握其邏輯有助於解決排列組合相關問題。關鍵在於從後向前尋找「轉折點」並進行局部調整。