Medium Monotonic Stack Stacks & Queues
In plain English: For each number in an array, find the first larger number to its right.
A monotonic stack maintains elements in decreasing order — when a larger element arrives, it 'resolves' all smaller elements on the stack.
Prompt
For each element, find the next element to its right that is larger.
Try to write it from scratch before scrolling down.
Solution
def next_greater(a):
res = [-1] * len(a)
stack = []
for i in range(len(a) - 1, -1, -1):
while stack and stack[-1] <= a[i]: # pop smaller elements: they found their answer
stack.pop()
if stack:
res[i] = stack[-1]
stack.append(a[i])
return res
# Test: next_greater([4,5,2,25]) == [5,25,25,-1]