題目連結:
題目意譯:
我們給定一個連結串列其中 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 設為其下一個較大之值。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。