Monotonic Stack (Next Greater)
MediumKeep a stack of indices with decreasing values. Every new element resolves the answer for everything it dominates.
stacklinear
TimeO(n)
SpaceO(n)
InputComma separated numbers
2
0
1
1
2
2
4
3
3
4
5
5
answer
-
-
-
-
-
-
For each element, find the first larger value to its right.
1 / 19
for i from 0 to n-1:
while stack and a[stack.top] < a[i]:
j = stack.pop(); ans[j] = a[i]
stack.push(i)
anything left on the stack has no greater element
Why it matters
Each index is pushed once and popped once, so the nested-looking loop is still linear.
Keyboard
space play← → stepr restartctrl K search
Next visualiser
Cyclic Sort