Given an array of integers temperatures, return an array answer such that answer[i] is the number of days you have to wait after day i to get a warmer temperature. If there is no future day for which this is possible, answer[i] == 0.
Example 1
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Explanation: Day 0 (73) waits 1 day for 74; day 2 (75) waits 4 days for 76.
1 <= temperatures.length <= 10^530 <= temperatures[i] <= 100The brute force checks every future day for each day — O(n^2). What if you only kept days that are still 'waiting' for a warmer day?
A monotonic (decreasing) stack of indices lets you resolve many waiting days the instant a warmer temperature shows up.
When the current temperature is warmer than the stack's top, that's the answer for every index you pop — not just one.
public int[] dailyTemperatures(int[] temperatures) {
int[] answer = new int[temperatures.length];
Deque<Integer> stack = new ArrayDeque<>(); // holds indices, temperatures decreasing bottom to top
for (int i = 0; i < temperatures.length; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int prevIndex = stack.pop();
answer[prevIndex] = i - prevIndex;
}
stack.push(i);
}
return answer;
}Time: O(n) · Space: O(n)