What Is a Monotonic Stack?

A monotonic stack is a stack whose elements are kept in a fixed order by value, usually decreasing from bottom to top. Every time you push, you first pop the elements that would break that order. Because the order is maintained, the top of the stack is always the element you are most likely to need, which is what removes the repeated scanning that makes naive solutions quadratic.

The problems it solves share a shape: you are looking for, for each element, some information about the elements around it, and the answer for one element becomes known exactly when a later element arrives. The classics are the next greater element, the daily temperatures problem, and the largest rectangle in a histogram, plus the next smaller element variants of all of them.

The mechanism is that the pop condition encodes the answer. In the next greater element, you pop while the top is smaller than the current value, and every popped index gets the current value as its answer. Because the stack is ordered, only the top can violate the condition, so the while loop terminates immediately once it is satisfied.

The trade-off to name is that a monotonic stack needs random access to the values behind the indices it holds. For an array that is free, but for a linked list or a stream you would have to store the values alongside the indices. The second point is that monotonic stacks are harder to debug than the naive version, because the invariant has to hold at every step, and a slightly wrong comparison operator produces plausible but wrong answers rather than an error.

Keep a stack of indices whose bars are in decreasing height. When a shorter bar arrives, every taller bar on the stack can no longer extend to the right, so you pop them and compute the rectangle each one could form.

def largest_rectangle(heights):
    stack = []
    best = 0
    for i, height in enumerate(heights + [0]):
        while stack and heights[stack[-1]] > height:
            h = heights[stack.pop()]
            left = stack[-1] if stack else -1
            width = i - left - 1
            best = max(best, h * width)
        stack.append(i)
    return best


print(largest_rectangle([2, 1, 5, 6, 2, 3]))
print(largest_rectangle([2, 4]))

The outputs are 10 and 4. In the first array the two bars of height five and six form a rectangle two wide and five high, which is ten, and no other rectangle is larger. In the second array the best is the single bar of height four.

The mechanism is that when a bar is popped, its height is the minimum over the span between the new top of the stack and the current position, so that span is the widest rectangle at that height. The sentinel zero appended to the end forces every remaining bar to be popped and considered. The width calculation uses the index below the popped one as the left boundary, which is the nearest bar that is shorter.

The trade-off to name is that this is linear only because each index is pushed and popped once, so the total work is proportional to the number of bars. The naive approach tries every possible left and right boundary and takes the minimum height in between, which is cubic. The other detail is that the sentinel height must be zero rather than something else, because a sentinel that is taller would leave bars on the stack that were never considered, and the final answer would be too small.

Push indices onto a stack, keeping the values behind them in decreasing order. Whenever the current value beats the value on top, that index is finished and gets the current value as its answer.

def next_greater(values):
    result = [-1] * len(values)
    stack = []
    for i, value in enumerate(values):
        while stack and values[stack[-1]] < value:
            result[stack.pop()] = value
        stack.append(i)
    return result


print(next_greater([2, 1, 4, 3]))
print(next_greater([3, 1, 2, 5]))

The outputs are 4, 4, minus one, minus one and 5, 2, 5, minus one. In the second array the 3 has no greater value after it, the 1 gets the 2, and the 2 gets the 5.

The mechanism is the pop condition. Because the values behind the stack indices are in decreasing order, only the top can be smaller than the current value, so the while loop examines exactly the indices that the current value settles. Every popped index receives the current value as its next greater element, and because it survived on the stack until now, nothing greater came along earlier.

The trade-off to name is that the stack holds indices so that the answer can be written into the right slot of the result array, and the values are read back through them. If you only need the values of the answers you could store the values directly and lose the index information, but then you could not report which position each answer belongs to. The comparison is strict, so equal values do not settle each other, and using less than or equal instead would change the answer for arrays with repeated values.