Monotonic Stack — the shape behind dozens of interview problems.

Monotonic Stack in Python

def next_greater(nums: list[int]) -> list[int]:
    out = [-1] * len(nums)
    stack: list[int] = []
    for i, v in enumerate(nums):
        while stack and nums[stack[-1]] < v:
            out[stack.pop()] = v
        stack.append(i)
    return out

See language-specific tabs at /languages/python/patterns and the SQL variant at /languages/sql/patterns.

Related patterns

Frequently asked questions

What is the monotonic stack pattern?

Monotonic Stack is a stack whose elements stay in non-increasing or non-decreasing order. Time O(n) amortized (each element is pushed and popped once).

When should I use monotonic stack?

Use it when: Next greater / previous smaller element queries. Histogram / skyline problems. You need to remember the last index where a condition held.

What are the most common monotonic stack bugs?

Using the wrong comparator (< vs <=) for duplicates. Forgetting to pop everything at the end to handle unresolved indices. Storing values instead of indices when the answer needs indices.

What problems use the monotonic stack pattern?

Representative scenarios: Next Rainy Day — days until next higher temperature. Skyline Vault — largest rectangle in a histogram. Convoy Merge — stock-span style cumulative count.

Is monotonic stack on the Blind 75?

Yes — Monotonic Stack is one of the core patterns behind the Blind 75 list. See /blind-75 for the complete mapping.