Monotonic Stack Example: How Far Back Each Building's View Reaches

The monotonic stack also finds the nearest earlier larger value, by reading the answer when each position is pushed instead of when it is popped. A street of seven buildings runs west to east with heights 5 3 2 4 6 1 3 in storeys, and a viewer on each roof looks west. They see over every shorter building until the first taller one, and the question is how many buildings each viewer sees over.

Nothing in the question says greater, but each answer is the distance to the previous taller building. Pop every waiting building shorter than the current one, since none of them can block a view from further east either. Whatever is left on top is the first taller building to the west, at index top, so the viewer sees over i − top − 1 buildings; with nothing left, they see over all i buildings to the west. The answer is a distance, so the stack holds indices.

The run prints 0 0 0 2 4 0 1. The stack's order is the same as for the next greater value, decreasing towards the top; what changed is when the answer is read. The next greater reads a position's answer when it is popped, and the previous greater reads it when it is pushed, from whatever is left beneath. The pass is O(n) time and O(n) extra space, by the same push-once, pop-once count.