Daily Temperatures

You are given an array of daily temperatures. For each day, return how many days you have to wait until a strictly warmer temperature occurs. If there is no future warmer day, return 0 for that position.

Input / output

• Input: temperatures: int[]
• Output: int[] where each entry is the wait until a warmer day

Examples

1. temperatures = [73,74,75,71,69,72,76,73] returns [1,1,4,2,1,1,0,0].
2. temperatures = [30,40,50,60] returns [1,1,1,0].
3. temperatures = [30,60,90] returns [1,1,0].

Constraints

• 1 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100

Target complexity

• Aim for O(n) time and O(n) extra space.

Hints

1. When you read a new temperature, it may answer several earlier days at once.
2. Keep unresolved days in a stack that stays decreasing by temperature.

Follow-up If an interviewer asked for the previous warmer day instead of the next warmer day, how would the direction of your scan and stack invariant change?