LeetCode Next Permutation：字典序下一排列原地算法

題目回顧

給定數組，原地修改為字典序下一個排列。若已是最大排列，重排為最小（升序）。要求 O(1) 空間。
例：[1,2,3] → [1,3,2]；[3,2,1] → [1,2,3]

核心算法：三步走

1. 從右向左找第一個降序對：nums[i] < nums[i+1]，記錄 i 為 pivot
2. 從右向左找第一個 > nums[pivot] 的元素，交換
3. 反轉 pivot 之後的子數組（原為降序，反轉變升序，即最小排列）

圖解例：[1,7,3,4,2,1]

1 7 3 4 2 1
    ↑
  pivot=3 (索引2, 值3)
從右找第一個 >3 的：4 (索引3)
交換：1 7 4 3 2 1
反轉 pivot 後：1 7 4 1 2 3

Python 代碼

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        pivot = -1
        # 步驟1：找 pivot
        for i in range(n-2, -1, -1):
            if nums[i] < nums[i+1]:
                pivot = i
                break
        if pivot == -1:  # 已是最大排列
            nums.reverse()
            return
        # 步驟2：找換位元素
        for i in range(n-1, pivot, -1):
            if nums[i] > nums[pivot]:
                nums[i], nums[pivot] = nums[pivot], nums[i]
                break
        # 步驟3：反轉後綴
        nums[pivot+1:] = reversed(nums[pivot+1:])

複雜度

• 時間：O(n)
• 空間：O(1)

關鍵點

• 「降序後綴」代表該後綴已是最大排列，需向前進位
• 交換後，後綴仍是降序，反轉即得最小後綴
• 邊界：全降序 → 直接反轉整個數組