31. Next Permutation

Next Permutation

題目描述：給定一個整數陣列 nums，請找出其字典序的下一個排列，並原地（in-place）修改陣列。若當前排列已是最大（即完全降序），則將其重置為最小排列（完全升序）。必須使用 O(1) 額外空間。

解題思路：觀察「下一個排列」的特性：我們希望找到一個比當前排列稍大一點的排列。要讓排列變大，需要在某個位置將一個較小的數換成右側的某個較大數，同時盡量讓右側維持最小（升序）。

具體步驟如下：

1. 找到「下降點」：從右向左掃描，找到第一個滿足 nums[i] < nums[i+1] 的位置 i。這是排列中最靠右的「不滿足降序」位置。若找不到（整個陣列為降序），代表當前是最大排列，直接翻轉整個陣列即可。

2. 找到交換目標：在 i 右側（區間 [i+1, n-1]）找到比 nums[i] 大的最小值。由於右側是降序排列，從右往左找第一個大於 nums[i] 的元素 j 即可。

3. 交換：將 nums[i] 和 nums[j] 互換，使得 i 位置的值變大。

4. 翻轉後綴：交換後，i+1 到末尾的部分仍是降序（因為我們找的是最小的大於 nums[i] 的值，交換後右側仍降序）。將其翻轉為升序，確保右側是所有可能中最小的排列，從而得到整體最接近的下一個排列。

時間複雜度：O(n) — 每個步驟（向左掃描找 i、向左掃描找 j、swap、reverse 後綴）最多遍歷陣列一次，總體線性時間。

空間複雜度：O(1) — 所有操作原地進行，只用常數個額外變數，符合題目的空間限制。

方法一：暴力產生所有排列 產生所有 n! 個排列並排序，找到當前排列在排序後列表中的下一個。時間複雜度 O(n! × n)，空間複雜度 O(n! × n)，對 n 稍大時完全不可行，僅有理論意義。

方法二：使用 C++ STL next_permutation C++ 標準庫的 std::next_permutation 內部實作的邏輯與本題解法完全相同（找下降點 → 找交換目標 → swap → reverse），但封裝成一行呼叫。競賽中可直接使用，但面試中通常需要手寫實作以展示理解。時間複雜度 O(n)，空間複雜度 O(1)。

1. 如果需要找「第 k 個下一排列」（即從當前排列往後跳 k 步的排列），你會如何高效實作？能否不需要逐步呼叫 k 次 nextPermutation？
2. 與本題對稱的問題是「前一個排列（Previous Permutation）」。請描述如何修改本演算法以實作 prevPermutation，步驟有何不同？
3. 給定兩個排列 A 和 B，如何計算 A 與 B 之間相差幾步（即需要呼叫幾次 nextPermutation 才能從 A 到達 B）？