基本資料#
難易度：Medium 第一次嘗試：2025-08-09
- 總花費時間：00:00.00
解題思路#
因為陣列是環狀的，可以把遍歷想成「走兩圈」。第一圈先盡量替每個索引找到下一個更大的元素；第二圈只負責把還沒找到答案的索引補齊。注意第二圈不需要再把索引推入棧中。
另一個乾淨的做法是從後往前遍歷 2n 次（從 2n-1 到 0），用遞減的單調棧維護索引。對於當前 idx = i % n，持續彈出小於等於當前值的索引；此時若棧非空，棧頂就是 idx 的下一個更大元素。利用取模自然地把首尾串起來處理環狀。
解法#
作法一：正向兩遍 + 單調遞減棧
- 想法：第一遍能填多少就填多少；第二遍只補齊剩下的索引，不再推入新索引。
- 複雜度：時間 O(n)、空間 O(n)。
作法二：反向遍歷 + 取模 + 單調遞減棧
- 想法：從 2n-1 迭代到 0，對
idx = i % n，先彈出較小或相等的元素；若棧頂存在，即為下一個更大元素。 - 複雜度：時間 O(n)、空間 O(n)。
收穫#
- 問題本質就是單調遞減棧的典型應用。
- 正向雙遍與反向單遍（配合取模）本質等價，依習慣擇一即可。
- 以「索引」入棧能妥善處理重複值。
遇到的問題#
- 第二遍若又把索引推入棧會破壞正確性與效率。
- 反向遍歷的邊界（2n-1 到 0）與取模容易出現 off-by-one，要小心。
- 比較條件需使用「<=」來正確處理重複值。