題目描述: 給定一個鏈結串列,移除所有右邊存在更大值的節點。也就是說,只保留那些從該節點到尾端沒有比它更大的值的節點。
解題思路: 從右往左看,我們需要維護一個「從右邊看到的最大值」。任何小於此最大值的節點都要被移除。
最直觀的做法是使用單調遞減棧:從左到右遍歷鏈結串列,維護一個遞減棧。對於每個節點,彈出棧中所有值小於當前節點值的節點(因為這些節點右邊存在更大值)。最後棧中剩下的就是答案。
也可以反轉鏈結串列,從頭開始維護最大值,然後再反轉回來。
時間複雜度:O(n) — 每個節點最多被壓入和彈出棧各一次
空間複雜度:O(n) — 棧最多儲存 n 個節點
1. Initialize empty stack
2. Traverse linked list from head:
a. While stack is not empty and top's value < current value:
- Pop stack (this node has a larger value to its right)
b. Push current node onto stack
3. Reconstruct list from stack:
a. Pop nodes one by one, linking each to the previous
b. Return the last popped node as new head反轉鏈結串列法:(a) 反轉鏈結串列,(b) 從頭遍歷,維護當前最大值,移除所有小於最大值的節點,(c) 再次反轉。時間 O(n),空間 O(1)(不需要棧)。
遞迴法:遞迴到尾端,返回時維護右側最大值。若當前值 < 右側最大值則跳過該節點。時間 O(n),空間 O(n)(遞迴棧)。程式碼最簡潔但有遞迴深度限制。