O(n) O(n)
Intuition
Each day j can "resolve" the wait time for earlier colder days. Keep a stack
of unresolved day-indices in decreasing temperature order. A warmer day pops
everyone it dominates.
Explanation
Approach
st = [](indices),ans = [0] * n.- For
iin rangen:- While
standtemps[i] > temps[st[-1]]:j = st.pop();ans[j] = i - j.
- Push
i.
- While
Walk-through
temperatures = [73,74,75,71,69,72,76,73]
| i | temp | stack before | pops/updates | stack after |
|---|---|---|---|---|
| 0 | 73 | [] | — | [0] |
| 1 | 74 | [0] | ans[0]=1 | [1] |
| 2 | 75 | [1] | ans[1]=1 | [2] |
| 3 | 71 | [2] | — | [2,3] |
| 4 | 69 | [2,3] | — | [2,3,4] |
| 5 | 72 | [2,3,4] | ans[4]=1, ans[3]=2 | [2,5] |
| 6 | 76 | [2,5] | ans[5]=1, ans[2]=4 | [6] |
| 7 | 73 | [6] | — | [6,7] |
Result: [1,1,4,2,1,1,0,0].
Implementation
import java.util.*;
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] ans = new int[n];
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && temperatures[i] > temperatures[st.peek()]) {
int j = st.pop();
ans[j] = i - j;
}
st.push(i);
}
return ans;
}
}