Monotonic stack

A monotonic stack is an ordinary stack with one extra rule: its values always go in one direction, for example always down from bottom to top. With that rule, many “find the next bigger value” questions can be answered in one pass.

The next bigger value

For each value in a list, find the first value to its right that is bigger. If there is none, the answer is −1. For [2, 7, 3, 5, 4, 6, 1] the answers are [7, -1, 5, 6, 6, -1, -1].

The direct way looks to the right from every place until it finds something bigger. When the list goes down, such as [9, 8, 7, …, 1], every search runs to the end, so the total is about n² / 2 steps (n multiplied by n, then halved): O(n²).

Keep a stack in order

Ask the question the other way. Walk from left to right, and keep a stack of places that are still waiting for their answer. When a new value arrives, it is the answer for every waiting place whose value is smaller. Those places are all at the top of the stack, so pop them.

Why does this stay true? A new value pops everything on top that is smaller, so when it is pushed, the value below it is at least as big. And why are the smaller values all at the top? Because the values go down towards the top, the first value that is not smaller stops the popping, and everything below it is bigger still.

Start with every answer set to −1 and an empty stack. Then, for each place i with value x, do this step:

while stack and a[stack[-1]] < x:
    answer[stack.pop()] = x     # x is the answer for that place
stack.append(i)                 # i now waits for its answer

Places still on the stack at the end keep −1. STAQ-P5 asks a question of this kind.

The stack holds places, not values, because the answer must be written at the right place. You can always read the value with a[place].

Why it is O(n)

There is a loop inside a loop, which often means O(n²): time that grows with n multiplied by n. Not here. Count the work by place instead of by pass: each place is pushed exactly once, and popped at most once. So there are at most n pushes and n pops in the whole run, however they are spread over the passes. The total is O(n).

This way of counting, where you add up the work over the whole run instead of taking the worst pass, is amortised analysis (BIGO-7). One pass may pop many places, but only because earlier passes pushed them without popping.

The same idea, other questions

• Next smaller value: keep the values going up from bottom to top, and pop while the top is bigger.
• Previous bigger value: when you push place i, the place just below it on the stack is the nearest bigger value to its left (or there is none, if the stack was empty).
• Distance instead of value: write i - place instead of x. “How many days until a warmer day?” is this question.
• Largest rectangle under a bar chart: each bar spreads left and right until it meets a shorter bar. The previous and next smaller bars give both edges, again in O(n).

Now try STAQ-P5, Next taller signal.