'Next greater element' for each array item in O(n) uses…
Options
- A monotonic stack (Correct option)
- A min-heap
- Binary search on a sorted copy
- A trie of the values
Answer
A monotonic stack
Why
Keep a stack of indexes whose next greater element is not known yet; their values are in decreasing order (that is why it is called 'monotonic').
When a new value is bigger than the top of the stack, it IS the answer for that item: pop it and record the answer. Repeat, then push the new index.
Each index is pushed and popped once: O(n).
Remember
'Next greater/smaller' → monotonic stack.