Description
For each daily temperature, report how many days pass before a strictly warmer day. Report zero if no later warmer day exists.
Solution
def daily_temperatures(temperatures):
waits = [0] * len(temperatures)
unresolved = []
for day, value in enumerate(temperatures):
while unresolved and temperatures[unresolved[-1]] < value:
previous = unresolved.pop()
waits[previous] = day - previous
unresolved.append(day)
return waitsExamples
Example 1
- Input
[[73,74,75,71,69,72,76,73]]- Output
[1,1,4,2,1,1,0,0]
Each answer measures the next strictly warmer day.
Example 2
- Input
[[30,40,50]]- Output
[1,1,0]
The first two days wait one day.
Example 3
- Input
[[50,50,40]]- Output
[0,0,0]
Equal or cooler later days do not count.
Approach
Keep a stack of unresolved day indices with nonincreasing temperatures. A warmer incoming day resolves all cooler days on top; their waits equal the difference in indices.
Time & space
O(n) time and O(n) auxiliary space, where n is the number of days.