class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int[n];
int i = 0;
int j = 1;
while (i < n && j < n) {
while (j < n && temperatures[j] <= temperatures[i]) {
j++;
}
if (j < n) {
res[i] = j-i;
}
i++;
j = i+1;
}
return res;
}
}
/*
1. two pinters
2. if find, the ans is (j-i), if next i, j set to i the same position
[55,38,53,81,61,93,97,32,43,78]
i
j
3 1 1 2 1 1
*/
mono stack (decresing, 注意要判斷 decresing or increasing
[73,74,75,71,69,72,76,73]
[1,1, 4, 2, 1, 1,0,0]
[ 75,71,69] in decresing stack , meets 72 > peek(), start to pop
T: O(n)
S: O(n), with ans result and stack
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int idx = stack.pop();
res[idx] = i - idx;
}
stack.push(i);
}
return res;
}
}
