Stacks and Queues Monotonic stack
211. Daily Temperatures
You are given an array of integers temperatures, where temperatures[i] is the reading on day i. For
each day, find how many days you wait after it until a warmer reading. Return the waits as an array answer
of the same length.
A day j is warmer than day i if temperatures[j] > temperatures[i]. An equal reading is not warmer.
answer[i] is j − i, where j is the first day after i that is warmer than it, so the next day counts
as a wait of 1. If no later day is warmer, answer[i] is 0.
Example 1
Input: temperatures = [14, 11, 12, 11, 16, 13, 15]
[4,1,2,1,0,1,0]Explanation: Day 0 (14) waits four days for the 16 on day 4, and day 2 (12) waits two days for it. Days 1 and 3 (both 11) and day 5 (13) each get a warmer reading the next day, and days 4 and 6 have no warmer day after them, so their answers are 0.
Example 2
Input: temperatures = [-3, -3, -5, -2]
[3,2,1,0]Explanation: Day 1 has the same reading as day 0, which is not warmer, so day 0 waits until the −2 on day 3. Negative readings compare as usual: −2 is warmer than −3 and −5.
Example 3
Input: temperatures = [30, 25, 25, 20]
[0,0,0,0]Explanation: The readings never rise, so no day has a warmer day after it and every answer is 0.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ temperatures.length ≤ 105-109 ≤ temperatures[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.