題目描述:給定一個循環陣列 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]。時間複雜度: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]。這個模式修改是否影響遍歷次數與時空複雜度?