Monotonic Stack
A stack kept sorted by popping while the top violates the order; answers next-greater queries in O(n).
Decision · step 3 of 15Monotonic Stack: Next greater element
3 is not greater than 4, so 4 keeps waiting. Push 3 on top of it.
What you will see
An incoming value pops everything smaller before landing.
Cost
| push with pops | O(1) amortized |
|---|---|
| Space | O(n) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.
Before this
Taught by the same lesson
Monotonic Stack covers these too, in the same run.