Next Greater Element
Scan with a monotonic stack; each pop resolves an element's answer.
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
Each new value pops smaller ones off the stack and becomes their answer.
Cost
| Best | O(n) |
|---|---|
| Average | O(n) |
| Worst | O(n) |
| 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, predict what happens next, try operations in any order.
Screen readers: Items announce position from the top or front and value; each step announces the operation and the new top or front.
Reduced motion: Items appear or disappear in place with a crossfade instead of sliding in or out.
Before this
Variants
- Previous Greater Element Scan left to right
- Next Smaller Element Same with the inequality flipped.
- Previous Smaller Element Flip both direction and inequality.
Taught by the same lesson
Monotonic Stack covers these too, in the same run.