The Monotonic Stack, Explained

A monotonic stack is an ordinary stack with one extra rule: its values are always in sorted order from bottom to top.

Before pushing a new value, you pop every value that would break the order. That single habit answers questions like "what is the next larger element?" for every position in one pass.

Increasing stack

Values grow from bottom to top. Each new value first pops everything larger than it.

Example: with the stack holding [1, 4, 6], pushing 3 pops 6 and 4, leaving [1, 3].

Every value that gets popped has just met the first smaller value to its right.

So an increasing stack is the tool for next smaller element problems.

It also finds the previous smaller element, which is whatever sits below a value once it is pushed.

Use it whenever you need the nearest smaller value on either side of each element.

Decreasing stack

Values shrink from bottom to top. Each new value first pops everything smaller than it.

Example: with the stack holding [9, 5, 2], pushing 7 pops 2 and 5, leaving [9, 7].

Each popped value has just found its next greater element, so this is the classic setup for "how many days until a warmer temperature".

Why it is fast

Every element is pushed exactly once and popped at most once, so the whole scan is O(n) even though there is a loop inside the loop.

The brute force alternative compares every element with every element to its right, which is O(n²).

Store indices instead of values when you need distances, such as the number of days between two temperatures.

When to reach for it

The problem asks about the nearest larger or smaller element to the left or right of every position, or about spans and ranges bounded by such elements.

You will not see it often, but when you do, it is very hard to come up with it on the spot.

answer = [-1] * len(nums)
stack = []                      # indices
for i, x in enumerate(nums):
    while stack and nums[stack[-1]] < x:
        answer[stack.pop()] = x
    stack.append(i)

answer = [-1] * len(nums)
stack = []
for i, x in enumerate(nums):
    while stack and nums[stack[-1]] > x:
        answer[stack.pop()] = x
    stack.append(i)