Daily Temperatures
Medium· monotonic stack· next greater
Problem
Given a list of daily temperatures, return for each day how many days you must wait for a strictly warmer one. If no warmer day follows, the answer for that day is 0.
Examples
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Constraints
- • 1 <= temperatures.length <= 10^5
- • 30 <= temperatures[i] <= 100
Hints & approach
Hint 1
Checking every later day for each day is O(n^2).
Hint 2
Keep indices of days that are still waiting for something warmer.
Hint 3
Store indices, not temperatures, so you can compute the distance.
Approachtry the hints first
Maintain a stack of indices whose temperatures are non-increasing from bottom to top. For each day i, while the temperature at the top index is lower than today's, pop index j and set answer[j] = i - j. Then push i. Anything still on the stack at the end keeps the default 0. Every index is pushed and popped at most once, so the total work is linear.
Time O(n) · Space O(n)