Given an array of integers temperatures represents 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.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Explanation:
- Day 0: temp 73, next warmer is 74 on day 1 → wait 1 day
- Day 1: temp 74, next warmer is 75 on day 2 → wait 1 day
- Day 2: temp 75, next warmer is 76 on day 6 → wait 4 days
- Day 6: temp 76, no warmer day → 0
Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]
For each temperature, we need to find the next day with a warmer temperature. A monotonic decreasing stack is perfect for "next greater element" problems.
The stack stores indices of temperatures in decreasing order. When we find a warmer temperature, we can resolve all cooler temperatures in the stack.
def dailyTemperatures(temperatures):
n = len(temperatures)
answer = [0] * n
stack = [] # stores indices
for i in range(n):
# While current temp is warmer than stack top
while stack and temperatures[i] > temperatures[stack[-1]]:
prev_index = stack.pop()
answer[prev_index] = i - prev_index
stack.append(i)
return answer
For [73, 74, 75, 71, 69, 72, 76, 73]:
i=0: temp=73, stack=[] → push 0, stack=[0]
i=1: temp=74 > 73, pop 0, answer[0]=1, push 1, stack=[1]
i=2: temp=75 > 74, pop 1, answer[1]=1, push 2, stack=[2]
i=3: temp=71 < 75, push 3, stack=[2,3]
i=4: temp=69 < 71, push 4, stack=[2,3,4]
i=5: temp=72 > 69,71, pop 4,3, answer[4]=1, answer[3]=2, push 5, stack=[2,5]
i=6: temp=76 > 72,75, pop 5,2, answer[5]=1, answer[2]=4, push 6, stack=[6]
i=7: temp=73 < 76, push 7, stack=[6,7]
Result: [1, 1, 4, 2, 1, 1, 0, 0]
For each temperature, scan forward until finding a warmer day.
def dailyTemperatures(temperatures):
n = len(temperatures)
answer = [0] * n
for i in range(n):
for j in range(i + 1, n):
if temperatures[j] > temperatures[i]:
answer[i] = j - i
break
return answer
Not recommended: O(n²) time complexity, but simpler to understand.
1/**
2 * Daily Temperatures
3 * Time: O(n) with monotonic stack, O(n²) brute force
4 * Space: O(n)
5 */
6
7import java.util.*;
8
9// Approach 1: Monotonic Decreasing Stack (Optimal - O(n))
10class Solution {
11 public int[] dailyTemperatures(int[] temperatures) {
12 int n = temperatures.length;
13 int[] answer = new int[n];
14 Deque<Integer> stack = new ArrayDeque<>(); // stores indices
15
16 for (int i = 0; i < n; i++) {
17 // While current temp is warmer than stack top
18 while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
19 int prevIndex = stack.pop();
20 answer[prevIndex] = i - prevIndex;
21 }
22
23 stack.push(i);
24 }
25
26 return answer;
27 }
28}
29
30// Approach 2: Brute Force - O(n²)
31class Solution2 {
32 public int[] dailyTemperatures(int[] temperatures) {
33 int n = temperatures.length;
34 int[] answer = new int[n];
35
36 for (int i = 0; i < n; i++) {
37 for (int j = i + 1; j < n; j++) {
38 if (temperatures[j] > temperatures[i]) {
39 answer[i] = j - i;
40 break;
41 }
42 }
43 }
44
45 return answer;
46 }
47}
48
49// Approach 3: Reverse iteration with stack
50class Solution3 {
51 public int[] dailyTemperatures(int[] temperatures) {
52 int n = temperatures.length;
53 int[] answer = new int[n];
54 Deque<Integer> stack = new ArrayDeque<>();
55
56 // Iterate backwards
57 for (int i = n - 1; i >= 0; i--) {
58 // Pop smaller or equal temperatures
59 while (!stack.isEmpty() && temperatures[i] >= temperatures[stack.peek()]) {
60 stack.pop();
61 }
62
63 // If stack not empty, top is next warmer
64 if (!stack.isEmpty()) {
65 answer[i] = stack.peek() - i;
66 }
67
68 stack.push(i);
69 }
70
71 return answer;
72 }
73}
74