MediumRating 1513

503. Next Greater Element II

arraystackmonotonic-stack

解題說明

Next Greater Element II

題目描述：給定一個循環陣列 nums，對每個元素找出下一個更大的元素（可以繞回陣列頭部繼續搜尋）；若整個循環中都不存在更大的元素，則回傳 -1。

解題思路：

與 Next Greater Element I 相比，本題的關鍵差異是循環：尋找下一個更大元素時可以繞回陣列起點。一個常見的技巧是遍歷兩次陣列，模擬將陣列複製一份接在後面的效果，即對 2n 個位置用 i % n 取實際索引。

使用單調遞減棧存索引，算法步驟：

初始化答案陣列 ans 全為 -1，初始化空棧 stk（存索引）。
遍歷 i 從 0 到 2n - 1：
- 令 j = i % n，取當前實際元素 nums[j]。
- 若 nums[j] 大於棧頂索引對應的元素，表示找到了棧頂的「下一個更大元素」：彈出棧頂索引 top，設 ans[top] = nums[j]，重複直到條件不滿足。
- 若 i < n（第一輪），將索引 j 推入棧（第二輪無需再加入新索引，避免重複處理）。
棧中剩餘的索引表示沒有更大元素，其對應 ans 值保持 -1。

以 nums = [1, 2, 1] 為例：

i=0（j=0，值 1）：棧空，推入索引 0。棧：[0]
i=1（j=1，值 2）：2 > nums[0]=1 → ans[0]=2，彈出；棧空，推入索引 1。棧：[1]
i=2（j=2，值 1）：1 < nums[1]=2，推入索引 2。棧：[1, 2]
i=3（j=0，值 1）：1 < nums[2]=1（不大於），不彈。
i=4（j=1，值 2）：2 > nums[2]=1 → ans[2]=2，彈出；2 == nums[1]=2（不大於），停止。
結果：ans = [2, -1, 2]。

C++ 解法

複雜度分析

時間複雜度：O(n) — 遍歷 2n 次，但每個索引最多入棧和出棧各一次，攤銷後整體為 O(n)。

空間複雜度：O(n) — 棧最多儲存 n 個索引（第一輪全部入棧且無元素被彈出的最壞情形，例如嚴格遞減陣列）。

虛擬碼

1. 令 n = nums 的長度，初始化 ans 陣列（長度 n，全為 -1），初始化空棧 stk（存索引）。
2. 遍歷 i 從 0 到 2n-1：
   a. 令 j = i mod n（實際索引）。
   b. 重複：若棧非空 且 nums[棧頂] < nums[j]，
      則設 ans[棧頂] = nums[j]，彈出棧頂。
   c. 若 i < n，將 j 推入棧（只在第一輪加入新索引）。
3. 棧中剩餘的索引對應 ans 值已為 -1，無需處理。
4. 回傳 ans。

其他解法

替代方法

方法一：暴力雙迴圈

對每個位置 i，向右循環掃描最多 n-1 步，找第一個大於 nums[i] 的元素。

時間複雜度：O(n²)｜空間複雜度：O(1)（不含輸出）

邏輯直觀，但 n 較大時（如 n = 10⁴）效能不足。

方法二：單調棧遍歷一次 + 二次補充

第一次遍歷時建立棧，第二次遍歷只用於「解決」第一次遍歷後棧中未找到答案的索引。效果等同於遍歷兩次，只是拆成兩個獨立迴圈，程式碼結構較清晰但本質相同。

時間複雜度：O(n)｜空間複雜度：O(n)

方法三：單調棧遍歷兩次（推薦，本題解法）

用 i % n 統一處理循環，一個迴圈完成兩次遍歷。第一輪入棧，第二輪僅彈出，簡潔高效。

時間複雜度：O(n)｜空間複雜度：O(n)

延伸思考

延伸問題

Next Greater Element I（LeetCode 496）：本題的非循環版本，且 nums1 是 nums2 的子集。思考兩題的差異：496 需要 hashmap 做查詢映射，503 直接在索引上操作；496 是線性陣列，503 需模擬循環。
Daily Temperatures（LeetCode 739）：同樣是「找下一個更大值」的單調棧題，但答案要求距離天數而非元素值，且是線性陣列。比較兩題棧中儲存的資訊（索引 vs 索引）及答案記錄方式。
若要找「下一個更小元素」的循環版本：只需將棧的維護方向反轉（改為單調遞增棧），彈出條件改為 nums[棧頂] > nums[j]。這個模式修改是否影響遍歷次數與時空複雜度？

MediumRating 1513

503. Next Greater Element II

arraystackmonotonic-stack

在 LeetCode 上作答 ↗

解題說明

Next Greater Element II

解題思路：

使用單調遞減棧存索引，算法步驟：

初始化答案陣列 ans 全為 -1，初始化空棧 stk（存索引）。
遍歷 i 從 0 到 2n - 1：
- 令 j = i % n，取當前實際元素 nums[j]。
- 若 nums[j] 大於棧頂索引對應的元素，表示找到了棧頂的「下一個更大元素」：彈出棧頂索引 top，設 ans[top] = nums[j]，重複直到條件不滿足。
- 若 i < n（第一輪），將索引 j 推入棧（第二輪無需再加入新索引，避免重複處理）。
棧中剩餘的索引表示沒有更大元素，其對應 ans 值保持 -1。

以 nums = [1, 2, 1] 為例：

i=0（j=0，值 1）：棧空，推入索引 0。棧：[0]
i=1（j=1，值 2）：2 > nums[0]=1 → ans[0]=2，彈出；棧空，推入索引 1。棧：[1]
i=2（j=2，值 1）：1 < nums[1]=2，推入索引 2。棧：[1, 2]
i=3（j=0，值 1）：1 < nums[2]=1（不大於），不彈。
i=4（j=1，值 2）：2 > nums[2]=1 → ans[2]=2，彈出；2 == nums[1]=2（不大於），停止。
結果：ans = [2, -1, 2]。

C++ 解法

複雜度分析

時間複雜度：O(n) — 遍歷 2n 次，但每個索引最多入棧和出棧各一次，攤銷後整體為 O(n)。

空間複雜度：O(n) — 棧最多儲存 n 個索引（第一輪全部入棧且無元素被彈出的最壞情形，例如嚴格遞減陣列）。

虛擬碼

1. 令 n = nums 的長度，初始化 ans 陣列（長度 n，全為 -1），初始化空棧 stk（存索引）。
2. 遍歷 i 從 0 到 2n-1：
   a. 令 j = i mod n（實際索引）。
   b. 重複：若棧非空 且 nums[棧頂] < nums[j]，
      則設 ans[棧頂] = nums[j]，彈出棧頂。
   c. 若 i < n，將 j 推入棧（只在第一輪加入新索引）。
3. 棧中剩餘的索引對應 ans 值已為 -1，無需處理。
4. 回傳 ans。

其他解法

替代方法

方法一：暴力雙迴圈

對每個位置 i，向右循環掃描最多 n-1 步，找第一個大於 nums[i] 的元素。

時間複雜度：O(n²)｜空間複雜度：O(1)（不含輸出）

邏輯直觀，但 n 較大時（如 n = 10⁴）效能不足。

方法二：單調棧遍歷一次 + 二次補充

時間複雜度：O(n)｜空間複雜度：O(n)

方法三：單調棧遍歷兩次（推薦，本題解法）

用 i % n 統一處理循環，一個迴圈完成兩次遍歷。第一輪入棧，第二輪僅彈出，簡潔高效。

時間複雜度：O(n)｜空間複雜度：O(n)

延伸思考

延伸問題

Next Greater Element I（LeetCode 496）：本題的非循環版本，且 nums1 是 nums2 的子集。思考兩題的差異：496 需要 hashmap 做查詢映射，503 直接在索引上操作；496 是線性陣列，503 需模擬循環。
Daily Temperatures（LeetCode 739）：同樣是「找下一個更大值」的單調棧題，但答案要求距離天數而非元素值，且是線性陣列。比較兩題棧中儲存的資訊（索引 vs 索引）及答案記錄方式。
若要找「下一個更小元素」的循環版本：只需將棧的維護方向反轉（改為單調遞增棧），彈出條件改為 nums[棧頂] > nums[j]。這個模式修改是否影響遍歷次數與時空複雜度？