Next Greater Element
Scan with a monotonic stack. Each pop resolves an element's answer.
Monotonic Stack: Next greater element
8 is greater than 5, so 8 is the next greater element of 5. Pop 5, which now has its answer.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(n)
Before this
Variants
- Previous Greater Element
- Next Smaller Element
- Previous Smaller Element
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Monotonic Stack covers these too, in the same run.