最終更新 1794541558

Interview prep notes

修正履歴 d93a6cd3791493d02ad4fdc0b00fb47d994c1386

monotonic-stack.md Raw

Monotonic Stack: The Pattern Behind "Next Greater Element" Questions

If a question asks for the next greater, previous smaller, or "how many days until a warmer temperature", a monotonic stack usually turns an O(n²) scan into O(n).

Core idea

Keep a stack of indices whose values are in sorted order (decreasing for "next greater"). When a new value breaks the order, it is the answer for every index you pop.

def daily_temperatures(temps):          # LeetCode 739
    ans = [0] * len(temps)
    stack = []                           # indices, temps decreasing
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            ans[j] = i - j
        stack.append(i)
    return ans

Each index is pushed and popped at most once, so the loop is O(n) even with the inner while.

Choosing the direction

Question asks for Stack keeps values Pop when new value is
Next greater decreasing greater
Next smaller increasing smaller
Previous greater decreasing greater or equal (answer = new top)

Harder problems that use it

  • Largest Rectangle in Histogram (84): increasing stack; when a bar is popped, its width runs from the new stack top to the current index.
  • Trapping Rain Water (42): popping a lower bar between two taller ones gives the water above it.
  • Sum of Subarray Minimums (907): previous-smaller and next-smaller distances give how many subarrays each element is the minimum of. Handle duplicates with < on one side and <= on the other.

How to explain it in the interview

Say why it is linear: "Every element enters and leaves the stack once." Then trace a 5-element example on the whiteboard; interviewers care more about the invariant than the code.


Disclosure: I work on Linkjob AI's coding interview assistant. This write-up is general practice material.