Daily Temperatures
Daily Temperatures is LeetCode 739 (Medium). Given an array temperatures, return an array answer where answer[i] is the number of days after day i until a strictly warmer temperature. If no warmer day comes, answer[i] is 0.
- Up to 10⁵ days, so scanning forward from every day (O(n²)) is too slow.
- Temperatures are between 30 and 100.
- 1 <= temperatures.length <= 10⁵
- 30 <= temperatures[i] <= 100
Intuition
Think of the days that have not yet seen a warmer day as waiting. When a new day arrives, it settles every waiting day that is colder than it, starting with the most recent one. Most recent first is exactly what a stack gives.
The stack also has a useful shape: its temperatures never rise from bottom to top, because a warmer day would already have settled the colder ones below it.
This problem asks "how many steps until the next larger value", which is the next greater element pattern: a monotonic stack of indices still waiting for an answer. The same stack solves Next Greater Element I and II, Online Stock Span (looking back instead of forward) and Largest Rectangle in Histogram.
Approach
Before reading on: in [73, 74, 75, 71, 69, 72, 76, 73], day 6 (76) settles several earlier days at once. Which ones, and in what order? What do the days still waiting have in common just before it arrives?
Start with zeros and an empty stack
answer = [0] * n already holds the right value for every day that never sees a warmer one, so those days need no extra work. The stack will hold the indices of days still waiting.
Settle every colder day on top
For day i, while the stack is not empty and the day on top is colder than temperatures[i], pop it as prev and set answer[prev] = i - prev. Use while, not if: one warm day can end the wait of a whole run of colder days.
Push today's index
When the top is not colder, the loop stops: every day below it is at least as warm, so none can be settled. Push i. Store the index, not the temperature, because the answer is a distance between days and the temperature can be read back from the array.
Return the answer
Days left on the stack never met a warmer day and keep their 0. Each index is pushed once and popped at most once, so the whole scan is O(n) time even though it contains a nested loop.
Daily Temperatures solution in Python | C++ | Java
while, not if.while, not if.while, not if.Common pitfalls
Using if instead of while
if stack and temperatures[stack[-1]] < temp:
prev = stack.pop()
answer[prev] = i - prevwhile stack and temperatures[stack[-1]] < temp:
prev = stack.pop()
answer[prev] = i - prevOnly the top day is settled. On [70, 60, 50, 80] day 3 settles day 2, but days 0 and 1 stay at 0 instead of 3 and 2.
Popping on equal temperatures
while stack and temperatures[stack[-1]] <= temp:
while stack and temperatures[stack[-1]] < temp:
An equal day is not warmer. On [70, 70, 80], <= settles day 0 with a wait of 1, but the right answer is 2.
Pushing temperatures instead of indices
stack.append(temp)
stack.append(i)
The answer is i - prev, a distance between days. A stack of temperatures has no way to tell where the waiting day was.
Complexity
Daily Temperatures FAQ
Can it be solved without a stack?
Yes. Fill answer from right to left: for day i, start at j = i + 1 and, while temperatures[j] <= temperatures[i], jump ahead by answer[j] (stop if it is 0). The jumps skip days already known to be too cold. It is still O(n) and uses no stack, but it is harder to explain than the stack.
Should the stack go left to right or right to left?
Both work. Left to right (this page) settles a waiting day when its warmer day arrives. Right to left keeps a stack of candidate future days, pops the ones that are not warmer, and reads the answer from the top. The work and the stack size are the same.