LeetCode 739 · Medium · Stack

Daily Temperatures

For each day's temperature, return how many days you must wait until a strictly warmer day. If no warmer day ever comes, the answer for that day is 0.

O(n)time
O(n)space
monotonic stackcooling days wait

1–16 integers, 30 to 100

res days to wait, filled in when a warmer day pops it

stackdays still waiting

public int[] dailyTemperatures(int[] temperatures) { int[] res = new int[temperatures.length]; Deque<int[]> stack = new ArrayDeque<>(); // {temp, index} for (int i = 0; i < temperatures.length; i++) { int t = temperatures[i]; while (!stack.isEmpty() && t > stack.peek()[0]) { int[] top = stack.pop(); res[top[1]] = i - top[1]; } stack.push(new int[]{t, i}); } return res;}
i, t
—
stack.peek()
—
stack
[]
res
—

Why it works

  1. Brute force looks ahead from every day until it finds a warmer one: O(n²) when temperatures keep falling.
  2. Key insight: turn it around. Instead of each day searching forward, let each new day answer the days that are waiting for it. Invariant: the stack holds the days with no answer yet, and their temperatures never rise from bottom to top. A day warmer than the top answers it, then the next one, until it meets a day at least as warm.
  3. O(n) time. The while loop looks nested, but every day is pushed once and popped at most once, so all the pops together cost O(n). The stack uses O(n) space when temperatures only fall.
  4. Pitfall: store indices, and use >. The answer is a distance, so the stack must remember where each day was. "Warmer" means strictly warmer: with >=, a tie would wrongly answer an equal day. Days left on the stack at the end keep their 0.
  5. Same pattern: Next Greater Element (496, 503), Online Stock Span (901), Car Fleet (853) and Largest Rectangle in Histogram (84) all keep a monotonic stack of items still waiting for their answer.