LeetCode 739 · Stack · concept: monotonic-stack
Problem
For each day, how many days until a warmer temperature? 0 if none comes.
[73,74,75,71,69,72,76,73] -> [1,1,4,2,1,1,0,0]
Approach 1 — brute force
For each day, scan forward to the next warmer day. O(n²) — too slow.
Approach 2 — monotonic stack (optimal)
Keep a stack of indices of days still waiting for a warmer day, with temperatures decreasing down the stack. Each new day resolves every waiting day it’s warmer than.
def dailyTemperatures(temps):
res = [0] * len(temps)
stack = [] # indices, temps decreasing
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t: # today is warmer than waiting days
j = stack.pop()
res[j] = i - j # distance to the warmer day
stack.append(i)
return resTime O(n), space O(n). Each index is pushed and popped once → amortized O(1) each.
Why it’s O(n) despite the nested while
An index enters the stack exactly once and leaves exactly once. The inner while does total work bounded by n pops across the whole run — the hallmark amortized argument of the monotonic stack.
Key insight
“Next greater/smaller element” → monotonic stack of unresolved indices. The stack holds items still waiting for their answer; a new element resolves all the pending items it dominates. This is the single most reusable stack pattern — Car Fleet, Largest Rectangle, and Trapping Rain Water are all variations.
Related
- concept: monotonic-stack
- prev: Generate Parentheses · next: Car Fleet
Software engineering
Infrastructure & security
Computer science
Hardware & engineering