The problem
Given daily temperatures, return an array answer where answer[i] is how many days after day i you must wait for a warmer day. If no warmer day comes, answer[i] is 0.
Examples
01
- Input
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
- Output
[1, 1, 4, 2, 1, 1, 0, 0]
02
- Input
temperatures = [30, 40, 50, 60]
- Output
[1, 1, 1, 0]
Constraints
- 1 ≤ temperatures.length ≤ 10⁵
- 30 ≤ temperatures[i] ≤ 100
The idea
Keep a stack of the days still waiting for a warmer day. Their temperatures only go down from bottom to top: a warmer day would have ended the wait of any cooler day beneath it.
When a new day arrives, it is the answer for every waiting day that is cooler — pop them, recording the distance. Then it joins the stack to wait itself. Each day is pushed once and popped at most once.
- Time
- O(n)
- Space
- O(n) — the stack
Solution · every language run against every case
class Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]: out = [0] * len(temperatures) stack = [] # days still waiting for a warmer one; their temperatures decrease for i, t in enumerate(temperatures): while stack and temperatures[stack[-1]] < t: j = stack.pop() out[j] = i - j # day i is the first warmer day after day j stack.append(i) return out