Algorithms and Data Structures · Middle · Question 21 of 75
What is a monotonic stack used for?
- 1Implementing a queue on top of two stacks
- ✓Correct answer: Next greater element for every item in O(n)
- 3Sorting an array of numbers in O(n) time
Explanation
The stack keeps indices whose values are decreasing. When a bigger value arrives, it pops the smaller ones: the new value is their "next greater" element. Each index is pushed and popped once, so the pass is O(n).