439. Wait for Warmth
A weather station writes down the noon temperature of every day of a long season. A hiker who is tired of the cold wants to know, for each day, how many days she must wait before a strictly warmer day arrives, so she can plan her trips.
Given the array temps, return an array of the same length whose entry i is the number of days from day i to the first later day whose temperature is strictly higher than temps[i]. If no later day is warmer, the entry is 0. The season can last up to 100,000 days, so rescanning the future from every day will not be fast enough.
Example 1
- Input:
- temps = [71,69,72,68,66,75,70,74]
- Output:
- [2,1,3,2,1,0,1,0]
- Explanation:
Day 0 (71) waits 2 days for 72. Day 1 (69) waits 1 day. Day 2 (72) waits 3 days for 75. Days 3 and 4 both wait for 75. Day 5 (75) never sees a warmer day, day 6 (70) waits 1 day for 74 and day 7 has nothing after it.
Example 2
- Input:
- temps = [12,12,8,15,15,3]
- Output:
- [3,2,1,0,0,0]
- Explanation:
Equal temperatures do not count as warmer, so day 0 waits 3 days for the 15, day 1 waits 2, day 2 waits 1, and the last three days have no warmer future day.
Constraints
1 ≤ temps.length ≤ 105
-100 ≤ temps[i] ≤ 100
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)