Given an array temperatures of daily temperatures, return an array answer where answer[i] is the number of days you have to wait after day i to get a strictly warmer temperature. If no warmer day comes later, answer[i] is 0.
- 1 <= temperatures.length <= 10^5
- 30 <= temperatures[i] <= 100
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force looks ahead from every day until it finds a warmer one: O(n^2) for a decreasing array. The insight is that days still waiting for an answer form a decreasing sequence: if a colder day sat above a warmer one, the colder day would have been resolved first. So we keep their indices on a monotonic stack. Each new day pops every waiting day that is colder, answering it immediately, and then waits itself. Every index is pushed and popped once.
Algorithm
- Create
answerfilled with 0 and an empty stack of indices. - For each day
i: while the stack is not empty andtemperatures[i] > temperatures[top], poptopand setanswer[top] = i - top. - Push
ionto the stack. - Days left on the stack never see a warmer day and keep 0.
O(n)Space: O(n)class Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]: answer = [0] * len(temperatures) stack = [] # indices still waiting, temperatures decreasing for i, t in enumerate(temperatures): while stack and t > temperatures[stack[-1]]: j = stack.pop() answer[j] = i - j # day i is the first warmer day for j stack.append(i) return answer