Stack/QueueStack & Queue

Monotonic Stack (Next Greater Element)

A stack whose elements are kept in sorted order by popping everything that would violate the order before each push.

Learn Monotonic Stack →
a
2
0
1
1
5
2
6
3
2
4
3
5
8
6
4
7
stack (bottom → top, indices)
next greater
?
0
?
1
?
2
?
3
?
4
?
5
?
6
?
7
1/24For each element find the next greater element to its right. Indices wait on a stack whose values are strictly decreasing top-to-bottom, so a new bigger value resolves everything smaller in one go.
Current elementWaiting on stackAnswer resolvedNo greater element
PseudocodeLearn Monotonic Stack →
1ans = [-1] * n; stack = []  # indices, values decreasing
2for i in 0 .. n-1:
3  while stack and a[stack.top] < a[i]:
4    ans[stack.pop()] = a[i]
5  stack.push(i)
6return ans
Variables
n8
stackSize0
Complexity
access O(1)
search O(n)
insert O(1)
delete O(1)
Speed