Description
Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.
For example, given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].
Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].
Solution
Stack, time O(n), space O(n)
stack中只存储在temperatures中的index即可。逆序访问temperature array，stack中元素自底向上越来越小。
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] days = new int[n];
Stack<Integer> stack = new Stack<>();
for (int i = n - 1; i >= 0; --i) {
while (!stack.empty() && temperatures[stack.peek()] <= temperatures[i]) {
stack.pop();
}
if (stack.empty()) {
days[i] = 0;
} else {
days[i] = stack.peek() - i;
}
stack.push(i);
}
return days;
}
}
