Monotonic Stack: Next Greater Element
Answer span queries in one pass.
The Next Greater Problem
For each number, you want the first bigger value to its right. Brute force is O(n squared), but a monotonic stack does it in one pass.
What Monotonic Means
A monotonic stack keeps its values in sorted order, here decreasing, so the moment that order would break we know an answer is found.
All lessons in this course
- Stacks for Matching Brackets
- Monotonic Stack: Next Greater Element
- Queues and collections.deque
- Sliding Window Maximum with Deque