题目描述:
请根据每日 气温
列表 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;
}
}
题目来源:力扣(LeetCode)