Monotonic Stack
A stack kept sorted by popping while the top violates the order. Answers next-greater queries in O(n).
Monotonic Stack: Next greater element
7 is greater than 1, so 7 is the next greater element of 1. Pop 1, which now has its answer.
Cost
- Push with pops
- O(1) amortized
- Space
- O(n)
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Monotonic Stack covers these too, in the same run.