Next Smaller Element
The nearest smaller value to the right.
Monotonic Stack: Next smaller element
2 is smaller than 6, so 2 is the next smaller element of 6. Pop 6, which now has its answer.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(n)
Before this
A variant of
Leads to
Topics that need this one first.
Taught by the same lesson
Monotonic Stack covers these too, in the same run.