將陣列重新排列成「字典序的下一個更大排列」。若已是最大排列（遞減），則回到最小排列（遞增）。必須原地修改、且只用常數額外空間。
Example:
Input: nums = [1,2,3] Output: [1,3,2]
Input: nums = [3,2,1] Output: [1,2,3]（已是最大 → 回到最小）
Input: nums = [1,1,5] Output: [1,5,1]
Intuition
TIP
核心思路：從右往左找到第一個「下降點」i（nums[i] < nums[i+1]），把它換成右側剛好比它大的數，再把後段反轉成最小。
- 後段若是遞減，代表它已是該前綴下的最大排列，無法再變大
- 找到下降點
i後，後段必為遞減；從右找第一個比nums[i]大的nums[j]交換 - 交換後後段仍遞減，反轉成遞增即得「最小的更大排列」
- 找不到下降點 → 整個遞減 → 直接反轉成遞增
Approaches
⭐ Three Steps: Find Drop → Swap → Reverse Suffix — O(n) / O(1)
- Idea: 一次從右掃描找轉折點，常數次交換與一次反轉即可
- Time:
O(n)- 最多兩次線性掃描 + 一次反轉 - Space:
O(1)- 原地操作
class Solution {
fun nextPermutation(nums: IntArray) {
var i = nums.size - 2
// 1) 從右找第一個下降點 i：nums[i] < nums[i+1]
while (i >= 0 && nums[i] >= nums[i + 1]) i--
if (i >= 0) {
// 2) 從右找第一個比 nums[i] 大的 nums[j]，交換
var j = nums.size - 1
while (nums[j] <= nums[i]) j--
swap(nums, i, j)
}
// 3) 反轉 i 之後的後段（無下降點則 i = -1，反轉全部）
reverse(nums, i + 1, nums.size - 1)
}
private fun swap(a: IntArray, i: Int, j: Int) {
val t = a[i]; a[i] = a[j]; a[j] = t
}
private fun reverse(a: IntArray, lo: Int, hi: Int) {
var l = lo; var r = hi
while (l < r) { swap(a, l, r); l++; r-- }
}
}Note: Why step 3 reverses instead of sorts
交換後，後段 i+1..end 仍維持遞減（因為 nums[j] 是後段中剛好大於 nums[i] 的數，換入 nums[i] 後不破壞單調性）。遞減序列要變最小只需反轉，不必 O(n log n) 排序，所以整體維持 O(n)。
🔑 Takeaways
- Pattern: 陣列原地操作 + 雙指針，靠「後段是否遞減」判斷可否再變大
- Key trick: 三步——找下降點、與右側恰好更大的數交換、反轉後段。記住反轉（非排序）即可保證 O(n)；無下降點時
i = -1，反轉全部正好回到最小排列