arrayscomplexitystacks
A monotonic stack is about order, not sorting
Anonymous
For next-greater-element queries, keep indices whose values are still waiting for a larger value. When a new value is larger, it answers the pending indices at the top. Each index enters and leaves the stack at most once, so the scan takes O(n) time.
0