LeetCode 31 Next Permutation 完整解法：字典序下一排列算法詳解

題目描述

實現 **下一個排列**：將數字序列重排為**字典序中比當前排列大的最小排列**。若不存在 (已是最大排列)，重排為**最小排列** (升序)。**必須原地修改**，O(1) 額外空間。

例：[1,2,3]→[1,3,2], [3,2,1]→[1,2,3], [1,1,5]→[1,5,1]。

核心算法：三步走

1. 從右向左找「拐點」：找到**最右**的位置 i，使得 nums[i] < nums[i+1]。
   若不存在 (整個數組非遞增)，說明已是最大排列，直接 **整體反轉** 為升序並返回。
2. 從右向左找「換位者」：在 i 右側 (遞減區間) 找**最右**的位置 j，使得 nums[j] > nums[i]。
   (因右側遞減，最右滿足條件者即為「比 nums[i] 大的最小值」)。
3. 交換 + 反轉尾部：交換 nums[i] 和 nums[j]，然後將 i+1 到末尾 **反轉** (由遞減變遞增)，得到最小增量。

完整 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. 找換位者
            while (j > i && nums[j] <= nums[i]) --j;
            swap(nums[i], nums[j]);
        }
        // 3. 反轉尾部 (i+1 到末尾)
        reverse(nums.begin() + i + 1, nums.end());
    }
};

Java 版本 (LeetCode 原題語言)

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 (j > i && nums[j] <= nums[i]) j--;
        swap(nums, i, j);
    }
    reverse(nums, i+1, n-1);
}
private void swap(int[] a, int i, int j) { int t=a[i]; a[i]=a[j]; a[j]=t; }
private void reverse(int[] a, int l, int r) { while(l

初始: [1, 3, 2]  (字典序: 132)
1. 找拐點: i=0 (nums[0]=1 < nums[1]=3)
2. 找換位者: j=2 (nums[2]=2 > 1, 且最右)
3. 交換: [2, 3, 1]
4. 反轉尾部 (i+1=1 到末尾): [2, 1, 3]  → 下一個排列 213 ✓

// 標準庫已實現
bool has_next = next_permutation(nums.begin(), nums.end());
// 返回 false 表示已是最大排列，且 nums 已重排為最小排列
// 完全符合題目要求，面試可先寫 STL 版，再手寫算法展示理解