程式面試：如何原地求下一個字典序排列？
面試官考察點
給定可能含重複值的整數陣列，請原地改成字典序嚴格較大的下一個排列；若目前已是最大排列，則改成升序的最小排列。
約束與邊界
- 只能使用 O(1) 額外空間，允許交換與反轉。
- 重複值不能被當成不同元素計數，但比較仍按數值進行。
- 陣列為空或只有一個元素時，操作保持不變。
- 必須是全域字典序的下一個排列，不能只交換相鄰元素。
找到最右側轉折點
從右向左找到第一個滿足「左值嚴格小於右值」的位置 i。右側已是非遞增後綴；若找不到轉折點，整個陣列降序，反轉即可得到最小排列。
交換後再最小化後綴
有轉折點時，從右向左找第一個大於 nums[i] 的元素 j。因為後綴非遞增，首次找到的就是最小可行較大值。交換 i 與 j，再反轉 i + 1 之後的後綴，使變化幅度最小。
30 秒回答框架
「我從右找第一個上升轉折點 i。若不存在，陣列已是最大排列，直接反轉。否則從右找第一個大於 nums[i] 的 j，交換兩者，再把右側後綴反轉成升序。後綴原本非遞增，所以這三步得到嚴格較大的最小候選，時間 O(n)、空間 O(1)。 」
回答前需要釐清的問題
- 是否要求原地修改？若允許額外空間，可以排序複製；原地要求決定反轉方案。
- 「下一個」按數字升序還是字串比較？負數與多位數時語意不同。
- 元素是否可能重複？重複值決定尋找嚴格大於而不是大於等於。
分步驟深入解答
設陣列為 [1,2,3]，轉折點是 1 的位置，交換後綴中最小的大於它的 2，得到 [2,1,3]，再反轉後綴仍為 [2,1,3]。對 [3,2,1] 找不到轉折點，反轉成 [1,2,3]。
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
j = n - 1
while nums[j] <= nums[i]:
j -= 1
swap(nums[i], nums[j])
reverse(nums, i + 1, n - 1)等值元素使用「大於等於」關係跳過轉折候選，使用「小於等於」關係跳過交換候選，保證變化嚴格增加。後綴反轉而非排序，是因為轉折點右側已經有序，反轉可在線性時間完成。
高品質示範回答
「字典序下一個排列要先讓盡可能靠右的位置變大，同時讓後綴盡可能小。我從右找最右的『左值嚴格小於右值』轉折點；從右找第一個大於它的值交換，接著反轉後綴。沒有轉折點表示已是最大排列，反轉整個陣列。掃描、交換和反轉都是 O(n)，只用常數變數。」
常見錯誤
- 從左找轉折點，讓更高位改變，跳過中間排列。
- 交換後直接結束，沒有把後綴變成最小順序。
- 用大於等於尋找交換值，重複值可能無法嚴格變大。
- 對後綴呼叫通用排序，空間或複雜度超出原地要求。
- 沒有處理完全降序陣列，回傳原陣列而不是最小排列。
錯誤表現與修正
對 [1,3,2] 若回傳 [3,1,2]，表示轉折點選得太靠左；正確結果是 [2,1,3]。對 [1,1,5] 若交換相等元素，表示嚴格比較邊界錯誤。
生產化實作
封裝只接受可變隨機存取序列的函式，讓反轉使用雙指標。若元素型別可能溢出比較或跨語言比較規則不同，在介面層明確排序關係與異常輸入策略。
驗證清單
測試空陣列、單元素、完全升序、完全降序、重複值、轉折在末端和多個最佳排列。對小陣列生成所有不重複排列，按字典序排序後逐個驗證函式輸出的下一個元素。
追問及應對
為什麼一定要找最右轉折點？
越靠右的轉折點代表越小的高位變化；在它右側尋找交換值並最小化後綴，才能得到目前排列之後的緊鄰排列。
後綴為什麼可以直接反轉？
轉折點是從右找到的，因此右側原本非遞增。交換較大值後，剩餘後綴仍可透過反轉恢復為升序最小狀態。
如果要求第 k 個下一個排列呢？
重複執行會產生 O(k n) 時間；若 k 很大，可研究計數排列、跳躍或直接按排名解碼，但需要額外組合計數與重複值處理。
評分標準
- 轉折點正確：從右尋找最右的嚴格上升位置。
- 交換正確：從右尋找第一個嚴格較大的值。
- 後綴正確：交換後反轉為最小升序。
- 邊界完整：覆蓋降序、重複、空陣列和單元素。
- 複雜度準確：O(n) 時間、O(1) 額外空間。
合規檢查
確認三步演算法、邊界案例與複雜度結論在回答中保持一致。
面試作答要點
先解釋「右側最小變化」，再寫轉折、交換和反轉三步；用重複值例子說明嚴格比較，最後給出複雜度和全排列對拍。
一句話總結
下一個排列透過最右轉折點、最小可行交換值與後綴反轉，在原地 O(n) 時間得到字典序緊鄰結果。