arrayscomplexitystacks
When does a monotonic stack pay off?
Anonymous
To find the next strictly greater value to the right, scan left to right and keep indices whose values are still waiting for an answer. Before pushing the current index, pop while its value is smaller; the current value answers each popped index. Every index is pushed and popped at most once, so the scan is O(n) with O(n) extra space. For next greater-or-equal, adjust the comparison.
0