題目描述:給定一個鏈結串列,回傳一個整數陣列,其中第 i 個元素為鏈結串列第 i 個節點的「下一個更大節點」的值。若不存在,則該位置為 0。
解題思路:
此題本質上是「Next Greater Element」問題在鏈結串列上的變體。核心困難在於鏈結串列無法隨機存取,但可以先將所有節點值轉存到陣列中,再用標準的單調棧算法求解。
兩步驟流程:
展開鏈結串列:遍歷鏈結串列,將所有節點的值依序存入陣列 vals,記錄長度 n,並初始化答案陣列 ans(全 0)。
單調遞減棧求 Next Greater Element:從左到右遍歷 vals,維護一個單調遞減棧(存索引)。當遍歷到 vals[i] 時,若它比棧頂索引對應的值大,說明找到了棧頂元素的「下一個更大值」,將棧頂彈出並更新 ans[top] = vals[i],重複直到棧空或棧頂值 >= vals[i],然後將 i 推入棧。
遍歷結束後,棧中剩餘的索引對應的元素沒有更大值,ans 中它們的位置保持 0。
時間複雜度:O(n) — 遍歷鏈結串列一次 O(n),每個索引最多被推入和彈出棧各一次,棧操作總計 O(n)。
空間複雜度:O(n) — vals 陣列、ans 陣列和棧各 O(n) 空間。
1. 遍歷鏈結串列,將所有節點值存入陣列 vals,記長度為 n
2. 初始化 ans[0..n-1] = 0,空棧 stk(存索引)
3. 從 i = 0 到 n-1 遍歷:
a. 當棧非空且 vals[棧頂] < vals[i] 時:
- ans[棧頂] = vals[i]
- 彈出棧頂
b. 將 i 推入棧
4. 棧中剩餘索引對應 ans 值保持 0(已初始化)
5. 回傳 ans第一次遍歷建立「節點位置 → 值」映射,第二次再做 Next Greater 查詢。相比本解法多一次鏈結串列遍歷且需要哈希表,實際效能較差。不推薦。
對每個節點,從其後繼節點線性掃描找第一個更大值。時間 O(n²),空間 O(1)(不含輸出)。對小輸入可行,但無法通過大測資。
理論上可以在鏈結串列上直接操作,棧存節點指標而非索引,並同時維護一個計數器作為索引。雖然省去展開步驟,但要同步維護索引較為繁瑣,且無法減少整體複雜度。展開成陣列後再用標準算法是最清晰的做法。
雙向查詢:若題目改為同時求每個節點的「下一個更大值」和「上一個更大值」,應如何修改?需要幾次掃描?
環形鏈結串列:若輸入是環形鏈結串列(最後一個節點指回第一個),「下一個更大值」可能出現在環的任何位置,應如何修改算法?提示:可將陣列複製一份接在後面,類似 LC 503「Next Greater Element II」的處理方式。
Next Greater Element 系列:LC 496 是在兩個陣列間查找,LC 503 是環形陣列,LC 739 是求距離,本題是鏈結串列版本。這四題的核心棧操作有何共同模式?請整理它們的異同。