# 1019. 鏈表中的下一個更大節點 ## 題目地址(1019. 鏈表中的下一個更大節點) <https://leetcode-cn.com/problems/next-greater-node-in-linked-list/> ## 題目描述 ``` <pre class="calibre18">``` 給出一個以頭節點 head 作為第一個節點的鏈表。鏈表中的節點分別編號為：node_1, node_2, node_3, ... 。 每個節點都可能有下一個更大值（next larger value）：對于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的選項中最小的那個。如果不存在這樣的 j，那么下一個更大值為 0 。 返回整數答案數組 answer，其中 answer[i] = next_larger(node_{i+1}) 。 注意：在下面的示例中，諸如 [2,1,5] 這樣的輸入（不是輸出）是鏈表的序列化表示，其頭節點的值為 2，第二個節點值為 1，第三個節點值為 5 。 示例 1： 輸入：[2,1,5] 輸出：[5,5,0] 示例 2： 輸入：[2,7,4,3,5] 輸出：[7,0,5,5,0] 示例 3： 輸入：[1,7,5,1,9,2,5,1] 輸出：[7,9,9,9,0,5,0,0] 提示： 對于鏈表中的每個節點，1 <= node.val <= 10^9 給定列表的長度在 [0, 10000] 范圍內 ``` ``` ## 前置知識 - 鏈表 - 棧 ## 公司 - 騰訊 - 字節 ## 思路 看完題目就應該想到單調棧才行，LeetCode 上關于單調棧的題目還不少，難度都不小。但是一旦你掌握了這個算法，那么這些題目對你來說都不是問題了。 如果你不用單調棧，那么可以暴力O(N2)O(N^2)O(N2)的時間復雜度解決，只需要雙層循環即可。但是這種做法應該是過不了關的。使用單調棧可以將時間復雜度降低到線性，當然需要額外的O(N)O(N)O(N)的空間復雜度。 顧名思義，單調棧即滿足單調性的棧結構。與單調隊列相比，其只在一端進行進出。為了描述方便，以下舉例及代碼以維護一個整數的單調遞減棧為例。將一個元素插入單調棧時，為了維護棧的單調性，需要在保證將該元素插入到棧頂后整個棧滿足單調性的前提下彈出最少的元素。 例如，棧中自頂向下的元素為 1，2，4，5 ，插入元素 3 時為了保證單調性需要依次彈出元素 : - 最開始棧是這樣的： \[5,4,2,1\] - 為了維護遞減特性，1,2 需要被移除。此時棧是這樣的： \[5,4\] - 我們將 3 push 到棧頂即可 - 此時棧是這樣的： \[5,4,3\] 用代碼描述如下： Python Code: ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">monoStack</span><span class="hljs-params">(list)</span>:</span> st = [] <span class="hljs-keyword">for</span> v <span class="hljs-keyword">in</span> list: <span class="hljs-keyword">while</span> len(st) > <span class="hljs-params">0</span> <span class="hljs-keyword">and</span> v > st[<span class="hljs-params">-1</span>]: st.pop() st.append(v) <span class="hljs-keyword">return</span> st monoStack([<span class="hljs-params">5</span>, <span class="hljs-params">4</span>, <span class="hljs-params">2</span>, <span class="hljs-params">1</span>, <span class="hljs-params">3</span>]) <span class="hljs-title"># output: [5, 4, 3]</span> ``` ``` ## 關鍵點 - 單調棧（單調遞減棧） - 單調棧的代碼模板 ## 代碼 Python Code: ``` <pre class="calibre18">``` <span class="hljs-title"># Definition for singly-linked list.</span> <span class="hljs-title"># class ListNode:</span> <span class="hljs-title"># def __init__(self, x):</span> <span class="hljs-title"># self.val = x</span> <span class="hljs-title"># self.next = None</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">nextLargerNodes</span><span class="hljs-params">(self, head)</span>:</span> res, st = [], [] <span class="hljs-keyword">while</span> head: <span class="hljs-keyword">while</span> len(st) > <span class="hljs-params">0</span> <span class="hljs-keyword">and</span> head.val > st[<span class="hljs-params">-1</span>][<span class="hljs-params">1</span>]: res[st.pop()[<span class="hljs-params">0</span>]] = head.val st.append((len(res), head.val)) res.append(<span class="hljs-params">0</span>) head = head.next <span class="hljs-keyword">return</span> res ``` ``` **復雜度分析** 其中 N 為鏈表的長度。 - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(N)O(N)O(N) ## 擴展 甚至可以做到 O(1)的空間復雜度，請參考[C# O(n) time O(1) space](https://leetcode.com/problems/next-greater-node-in-linked-list/discuss/267090/C-O(n)-time-O(1)-space>) ## 相關題目 - [毎日一題 - 739.Daily Temperatures](https://github.com/azl397985856/leetcode/blob/master/daily/2019-06-06.md)