前往
大廳
主題

LeetCode - 1019. Next Greater Node In Linked List 解題心得

Not In My Back Yard | 2021-04-21 00:00:11 | 巴幣 0 | 人氣 230

題目連結:


題目意譯:
我們給定一個連結串列其中 head 作為其第一個節點。將串列中的節點命名為 node_1、node_2、node_3、…… 以此類推。

每個節點可能有著下一個較大的值:對於 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 ≦ node.val ≦ 10 ^ 9 對於每個連結串列中的節點 node。
給定的串列長度在範圍 [0, 10000] 中。



範例測資:
範例 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]


解題思維:
參見這題的核心想法(基本上該題除了要求的格式不太一樣以外,跟本題其實差不多)。

在本題中也是利用一個堆疊(Stack)維護一個遞減數列,然後同時記錄數列中每個值原先的索引值。

然後當有新的元素 x > 堆疊頂端時就將頂端移除直到頂端不再小於 x 時(或是直到堆疊為空),期間將被移除的元素根據其索引值將 x 設為其下一個較大之值。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作