題目敘述
輸入給定一個鏈結串列的head node。
要求我們進行化簡，只要某個節點的右手邊存在比較大的節點，就刪除掉。
例如 5->2->13->3
5的右手邊有13，所以5刪除掉。
2的右手邊有13，所以2刪除掉。
13的右手邊沒有更大的節點，所以13留著。
3的右手邊沒有更大的節點，所以3留著。
最後輸出為13->3。
測試範例
Example 1:
Input: head = [5,2,13,3,8]
Output: [13,8]
Explanation: The nodes that should be removed are 5, 2 and 3.
- Node 13 is to the right of node 5.
- Node 13 is to the right of node 2.
- Node 8 is to the right of node 3.
Example 2:
Input: head = [1,1,1,1]
Output: [1,1,1,1]
Explanation: Every node has value 1, so no nodes are removed.
約束條件
Constraints:
- The number of the nodes in the given list is in the range
[1, 10^5].
節點總數目介於 1 ~ 十萬之間。
1 <= Node.val <= 10^5
每個節點的節點值也介於 1 ~ 十萬之間。
演算法 DFS遞迴解
這題的關鍵其實就隱藏在化簡規則裡。
題目說:
某個節點的右手邊只要有比較大的節點，就刪除掉。
白話講，可以這麼說，通則就是
如果右邊有人比我(當下的節點)還大，則只保留右邊(相當於下個鄰居)。
如果右邊沒有人比我大，則我自己保留下來，並且保留原本的連接。
初始條件，也可以說 終止條件，什麼時候停下來?
當遇到空節點的時候，代表已經拜訪到串列的尾端，化簡流程結束。
示意圖
程式碼 DFS遞迴解
class Solution:
def removeNodes(self, head):
## Base case:
# Empty node or empty list
if not head:
return head
## General cases:
# Use the same pattern to carry out reduction
head.next = self.removeNodes(head.next)
# Next neighbor is larger than me, then keep neighbor alive
if head.next and head.next.val > head.val:
return head.next
else:
# Next neighbor is smaller than or equal to me, then keep myself alive
return head
複雜度分析
時間複雜度: O(n)
線性掃描，從左到右掃描每個節點，總共耗時O(n)
空間複雜度: O(n)
線性掃描，從左到右掃描每個節點，遞迴call stack最大深度為O(n)
關鍵知識點
這題的關鍵其實就隱藏在化簡規則裡。
題目說:
某個節點的右手邊只要有比較大的節點，就刪除掉。
白話講，可以這麼說，通則就是
如果右邊有人比我(當下的節點)還大，則只保留右邊(相當於下個鄰居)。
如果右邊沒有人比我大，則我自己保留下來，並且保留原本的連接。
