For each day, count the wait until a warmer one. Keep a stack of days still waiting; a warm day pops every colder day below it.
▼The problem
LeetCode 739 (Medium). 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 warmer temperature, or 0 if no future day is warmer.
Examples (LeetCode's): [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0], [30,40,50,60] → [1,1,1,0] and [30,60,90] → [1,1,0].
The solution
def dailyTemperatures(temps):
ans = [0] * len(temps)
stack = [] # days still waiting
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
ans[j] = i - j
stack.append(i)
return ansTranscript
Daily Temperatures. Given each day's temperature, how many days until a warmer one? If a warmer day never comes, the answer is zero.
Take seventy-three, seventy-four, seventy-five, seventy-one, sixty-nine, seventy-two, seventy-six, seventy-three. The answers: one, one, four, two, one, one, zero, zero. Rising days, like thirty, forty, fifty, sixty, each wait just one, except the last.
The easy way: from each day, scan forward until something is warmer. But in a long cold spell, every scan runs to the end, so that's order n squared time.
The trick is a stack of days still waiting. Picture each waiting day as a snowball, sized by its temperature, stacked into a snowman: smaller on top of bigger. When a warmer day arrives, every colder snowball on top melts. Its wait is today minus its own day. Then today joins the stack.
In code, walk the days. While the top of the stack is colder than today, pop it, and set its answer to i minus j. Then push today.
Seventy-three waits. Seventy-four melts it: one day. Seventy-five melts seventy-four: one day. Seventy-one and sixty-nine stack up. Seventy-two melts sixty-nine, one day, then seventy-one, two days. Seventy-six melts seventy-two, one day, then seventy-five, four days. The last two never melt, so they stay zero.
Each day is pushed once and popped at most once, so it's order n time, and the stack holds at most n days, so order n space.
Stack, melt, answer. That's Daily Temperatures.