Stack Solution
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def nextLargerNodes(self, head: ListNode) -> List[int]:
""" tc O(N) sc O(N)
idx 0 1 2 3 4 5 6 7
val 1,7,5,1,9,2,5,1
ans 7 9 9 9 0 5 0 0
[1] [7 5 1 ] [9 2 ] [9 5 1 ]
7
three cases 1. currenct node <= st[-1]
2. current node val > st[-1]
3. no later node that's bigger => res[i]= 0
"""
st = [] # [val,cnt]
cnt = 0 # n of list
nextval_idx = []
while head:
if not st:
st.append([head.val,cnt])
cnt += 1
head = head.next
else:
while st and st[-1][0] < head.val:
nextval_idx.append([head.val,st[-1][1]])
st.pop()
if st and st[-1][0] >= head.val:
st.append([head.val,cnt])
cnt += 1
head = head.next
res = [0]*cnt
for val, idx in nextval_idx:
res[idx] = val
return res s
#########################short version##########################
st = [] # [val,cnt]
cnt = 0 # n of list
res = []
while head:
while st and st[-1][0] < head.val:
res[st.pop()[1]] = head.val
st.append([head.val,len(res)])
res.append(0) # occupy space for currentn head.val
head = head.next
return res