Days until a warmer one
For each day, count how many days you must wait for a warmer temperature, by keeping the days still waiting on a stack and answering them with distances. About 14 minutes.
Answer with a distance
This is the previous step with a different answer. For each day you want the number of days until a warmer one. When a warmer day i arrives and pops a waiting day j, the wait is the number of days between them, which is i minus j.
So the stack stores positions of days, not temperatures. The temperature of a waiting day is looked up from its position when needed.
while stack and temps[stack[-1]] < t:
j = stack.pop()
res[j] = i - jDay 1 is 74, warmer than waiting day 0 (73). Day 0 waits 1 day. Day 1 now waits.
Never warmer means zero
A day with no warmer day after it is never popped. The problem asks for 0 in that case, so fill the answers with zeros first, and the days left on the stack at the end are already right.
The equal case matters too. A day that is only as warm as a waiting day does not answer it, since the wait is until a warmer day. Compare strictly.
res = [0] * len(temps) stack = []
Day 3 is warmer than waiting day 1. How many days does day 1 wait?
- A2
- B3
- C1
Show the answer
2. The distance is 3 minus 1.
Daily temperatures
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. If there is no future day with a warmer temperature, answer[i] is 0.
temperatures = [73, 74, 75, 71, 69, 72, 76, 73] → [1, 1, 4, 2, 1, 1, 0, 0]
1 ≤ length of temperatures ≤ 100,000 · 30 ≤ temperatures[i] ≤ 100