MediumVery High Frequency35 min
Monotonic Stack
Find next/previous greater/smaller elements in O(n) using a maintained ordering.
Keep a stack that is always sorted (monotonically increasing or decreasing). When an element breaks the order, pop — and that pop gives you the answer.
The Monotonic Stack
Operations — Step by Step
Next Greater Element
O(n)Each element pushed/popped once — O(n) amortizedStep-by-step1 / 6
Input stream
Invariant
Keep unresolved elements on the stack until a larger value resolves them.
Stacktop
0
i=0: push 2. Stack=[0]
Stack empty. Push index 0 (val=2). No pops.