Problems
Daily Temperatures
Medium·Tagsarraystackmonotonic-stack
Problem Statement
Given an array of integers `temperatures` representing the daily temperatures, return an array `answer` such that `answer
[i]` is the number of days you have to wait after the `ith` day to get a warmer temperature.
If there is no future day for which this is possible, keep `answer[i] == 0` instead.Examples
Example 1
Input
temperatures: [73, 74, 75, 71, 69, 72, 76, 73]Output
"[1, 1, 4, 2, 1, 1, 0, 0]"Why
Day 0 (73) warms up the very next day (74), a wait of 1. Day 2 (75) is not beaten until day 6 (76), a wait of 4. The last two days never get warmer, so each records 0.
Example 2
Input
temperatures: [30, 40, 50, 60]Output
"[1, 1, 1, 0]"Why
Each reading is higher than the one before, so every day waits a single day for the next warmer one, and the final day records 0 because nothing follows it.
Example 3
Input
temperatures: [30, 60, 90]Output
"[1, 1, 0]"Why
Temperatures climb at every step, so the first two days each wait one day for a warmer reading while the last day has no future day and records 0.
Constraints
- •1 <= temperatures.length <= 10^5
- •30 <= temperatures[i] <= 100
Hints
Stuck? Reveal a nudge toward the right pattern, one step at a time.
Hint 1
A brute force approach would look at every day, and then scan forward to find the next warmer day. This takes O(N^2) time. Can we do it in O(N)?
Hint 2
Instead of looking forward, what if we use a stack to 'remember' the days we haven't found a warmer day for yet?
Hint 3
If the current day's temperature is warmer than the temperature of the day at the top of the stack, we found the answer for the day at the top of the stack!
Hint 4
Store the *indices* of the days in the stack, not the temperatures themselves. This allows you to easily calculate the distance (number of days) by subtracting the popped index from the current index.