题目描述:请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。 示例 1:输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:输入: temperatures = [30,60,90]
输出: [1,1,0]
提示:- 1 <= temperatures.length <=
- 30 <= temperatures[i] <= 100
题目分析:这道题考察单调栈的知识，使用单调栈解决这道题很方便。首先，我们创建一个栈作为单调栈，因为题目要求的是升温的天数，而不是升温后的温度，因此栈中应该存储下标，而非温度。然后从左向右遍历每日温度，若栈为空或者当日温度小于等于栈顶温度则直接入栈。否则，若当日温度大于栈顶温度，说明栈顶元素的升温日已经找到了，则将栈顶元素出栈，计算其与当日相差的天数即可。 题解:执行用时: 32 ms 内存消耗: 47.8 MB class Solution {
public int[] dailyTemperatures(int[] temperatures) {
// 获取天数
int n = temperatures.length;
// 结果数组
int[] res = new int[n];
// 单调栈
Stack<Integer> stack = new Stack<>();
// 循环遍历每日温度数组
for (int i = 0; i < n; ++i) {
// 当栈非空
while (!stack.empty()) {
// 获取栈顶元素值
int index = stack.peek();
// 如果当前温度 小于等于 栈顶温度
if (temperatures[i] <= temperatures[index]) {
// 退出循环
break;
}
// 否则弹出栈顶元素
stack.pop();
// 并把日期差填入结果数组相应位置上
res[index] = i - index;
}
// 栈为空就把当前日期压入栈中
stack.push(i);
}
// 返回结果数组
return res;
}
}
|
