Daily Temperatures
Problem
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.
Examples
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.
Constraints
- •
1 <= temperatures.length <= 10^5 - •
30 <= temperatures[i] <= 100
Hints
Hint 1
The 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?
Hint 2
A monotonic (decreasing) stack of indices lets you resolve many waiting days the instant a warmer temperature shows up.
Hint 3
When the current temperature is warmer than the stack's top, that's the answer for every index you pop — not just one.
Solutions
public int[] dailyTemperaturesBruteForce(int[] temperatures) {
int[] answer = new int[temperatures.length];
for (int i = 0; i < temperatures.length; i++) {
for (int j = i + 1; j < temperatures.length; j++) {
if (temperatures[j] > temperatures[i]) {
answer[i] = j - i;
break; // first warmer day found — stop scanning forward for this i
}
}
}
return answer;
}Time: O(n^2) · Space: O(1) extra beyond the output