Given a list of daily temperatures T, return a list such 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 of temperatures T = [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
- 使用递减栈Descending Stack来做，栈里只有递减元素的
index. - 思路如下：
-- 遍历数组，如果栈不空，且当前数字大于栈顶元素，那么如果直接入栈的话就不是递减栈了，所以取出栈顶元素。 由于当前数字大于栈顶元素的数字，而且一定是第一个大于栈顶元素的数，直接求出下标差就是二者的距离。
-- 然后在循环中继续看新的栈顶元素，重复以上步骤，直到当前数字小于等于栈顶元素停止。然后将数字入栈，这样就可以一直保持递减栈，且每个数字和第一个大于它的数的距离也可以算出来。
-- 如果当前数字小，则直接入栈。
class Solution {
public int[] dailyTemperatures(int[] T) {
if (T == null || T.length == 0) {
return new int[0];
}
int[] result = new int [T.length];
//descending stack, for index of the element
Stack<Integer> tracker = new Stack<> ();
for (int i = 0; i < T.length; i++) {
while (!tracker.isEmpty () && T[i] > T[tracker.peek ()]) {
result[tracker.peek ()] = i - tracker.peek ();
tracker.pop ();
}
tracker.push (i);
}
return result;
}
}
