# 1019. Next Greater Node In Linked List

###### tags: `Leetcode` `Medium` `MonotonicStack` `LinkedList`

---
要找的是往右看離自己最近比自己大的，所以可以用嚴格遞增的單調棧。當獲得了鏈表下一個值，並將其與堆棧中所有元素（從最上面的元素開始）進行比較。如果在堆棧中找到一個小於當前值的元素，則將其從棧中彈出，並將其值設置為當前值。

單調棧迫使您尋找下一個最大值。如果找到了下一個最大值，則將棧中比它小的彈出，因此堆棧中剩餘的值將大於找到的任何其他值。同樣，堆棧中的值必須按降序排列，因為如果再次發現較大的值，它們將已經從堆棧中彈出。

因此，算法如下：

創建一個將返回的答案數組，但默認值為0
創建一個棧
開始遍歷鏈錶的每個節點。
對於每個值，將此值與堆棧頂部進行比較。如果它大於堆棧上的值，則將比它小的彈出，大魚吃小魚的概念，並獲取該值的索引，然後直接使用當前值在答案數組中對其進行更新。對棧中小於curr.val的每個值重複
將其值和index放入棧，然後移至下一個值。
當您到達節點的末尾時，不論如何往右也找不到比較大的值。由於這些索引的答案數組已經設置為0，因此可以立即返回。

https://leetcode.com/problems/next-greater-node-in-linked-list/discuss/313587/Python-97-solution-with-detailed-explanation

Time $O(n)$ (amortized)
Space $O(n)$

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def nextLargerNodes(self, head: ListNode) -> List[int]:
        # initializing the position 
        index = 0
        stack = []
        
        # List[int] to be returned
        ans = [] 
        
        #traverse the linked list till you reach the end of it 
        while head:
            #appending a zero when we start with the head
            ans.append(0)
            # If the stack has some value and the top of stack has value less than the current linked list node value, 
            # pop the stack and insert the value of current node at that index, 
            # do that till the stack is empty. This means for all the values on the left, current value is the next greater
            while stack and stack[-1][1] < head.val:
                idx, _ = stack.pop()
                ans[idx] = head.val
                
            #push the (index, head.val on the stack to compare with on the next iteration)
            stack.append((index, head.val))
            # increment the index
            index += 1
            head = head.next
        return ans