Monotonic StackMonotonic stacks

01Why it exists

Reach for it when you see:Next greater or smaller, the first one taller than this, left and right boundaries, each element looking rightward, an O(n²) double loop that only looks for the first element satisfying a condition.

02The core idea

A monotonic stack is an ordinary stack with one extra rule: its contents always stay increasing or always stay decreasing. Before pushing a new element, pop everything that would break that order. The moment an element is popped is the moment it finds its answer, because the new element is the first one to its right that is larger (or smaller).

Take "next greater element". The stack decreases from bottom to top and holds indices. A new element x arrives: every element on top that is smaller than x has x as its answer, so pop them one by one and record it, then push x. What remains on the stack is still waiting for something larger. Each index is pushed exactly once and popped at most once, so the whole sweep is O(n) — one factor of n cheaper than the brute-force O(n²).

How direction maps to monotonicity: for the first larger element on the right, use a decreasing stack and sweep left to right; for the first smaller element on the right, use an increasing stack; and for the first larger or smaller element on the left, there is no need for a second sweep, because it is simply the new top at the moment of the pop. The largest-rectangle problem gets both boundaries at once precisely because of this.

Equality is worth thinking through. For "strictly greater", pop with < and leave equal elements on the stack; for "greater than or equal", pop with <=. The histogram problem appends a sentinel bar of height 0 so that every remaining bar is popped and settled at the end.

03The algorithm

1. 1Confirm that the problem is "for each element, find the first element in some direction that satisfies a size condition".
2. 2Pick the direction of monotonicity: decreasing stack when looking for something larger, increasing when looking for something smaller. Store indices on the stack so you can compute distances and look values up.
3. 3Left to right, for each i: while stack and condition(nums[stack[-1]], nums[i]), pop the top j and record ans[j] (the answer is either i or nums[i]).
4. 4Push i. If you also need "the first one on the left", the new top at the moment j is popped is j's left boundary.
5. 5Whatever is still on the stack after the sweep has no answer (set it to −1 or 0). When everything has to be settled, append a sentinel value at the end.

04Interactive demo

Daily temperatures. Yellow marks the days still on the stack waiting for an answer; when a new day is warmer than the top, that top is popped and its answer filled in (green). Notice that the temperatures on the stack always decrease from bottom to top.

05Code

Daily temperatures, the general next greater element, and the largest rectangle in a histogram, which uses both boundaries at once. All three share the same skeleton; only the pop condition and what gets recorded on the pop change.

# Daily Temperatures (LeetCode 739): how many days until it gets warmer
# The stack holds indices whose temperatures decrease from bottom to top
def daily_temperatures(temps):
    ans = [0] * len(temps)
    stack = []                                   # days still waiting for an answer
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:    # today is warmer than the top
            j = stack.pop()
            ans[j] = i - j                       # today is day j's answer
        stack.append(i)
    return ans                                   # whatever is left on the stack stays 0


# General next greater element: the first larger value to the right of each position (-1 if none)
def next_greater(nums):
    ans = [-1] * len(nums)
    stack = []
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            ans[stack.pop()] = x
        stack.append(i)
    return ans


# Largest rectangle in a histogram (LeetCode 84): for each bar, find the first shorter bar on each side
def largest_rectangle(heights):
    heights = heights + [0]                      # sentinel that forces every bar out at the end
    stack = []                                   # increasing stack
    best = 0
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] >= h:
            top = stack.pop()
            left = stack[-1] if stack else -1    # first shorter bar on the left
            width = i - left - 1                 # the first shorter bar on the right is i
            best = max(best, heights[top] * width)
        stack.append(i)
    return best

06Practice

• LeetCode 739Daily TemperaturesMedium
• LeetCode 496Next Greater Element IEasy
• LeetCode 503Next Greater Element II (circular: sweep twice)Medium
• LeetCode 901Online Stock SpanMedium
• LeetCode 84Largest Rectangle in HistogramHard
• LeetCode 42Trapping Rain Water (the monotonic stack version)Hard