单调栈
解题思路
遍历每日温度，维护一个单调递减的栈，用单调递减的栈存储元素，找到比栈顶元素大的温度；
- 若栈为空 或者 当日温度小于等于栈顶温度，则直接入栈；
- 若栈不为空，当日温度大于栈顶元素，说明栈顶元素的升温日找到了，出栈并计算天数，继续判断栈顶元素；
因为求的是天数，所以栈中存储的是 索引下标；
图解
复杂度
-
时间复杂度：
O(n)，其中 n 是温度列表的长度，正向遍历温度列表一遍，对于温度列表中的每个下标，最多有一次进栈和出栈的操作； -
空间复杂度：
O(n)，其中 n 是温度列表的长度，需要维护一个单调栈存储温度列表中的下标；
代码实现
var dailyTemperatures = function (temperatures) {
// 单调递减栈
let stack = [];
let n = temperatures.length;
let res = new Array(n).fill(0);
// 遍历每日温度，维护一个单调栈
for (let i = 0; i < n; i++) {
// 当日温度大于栈顶温度，说明栈顶温度的升温日找到了，栈顶出栈并计算天数；继续判断栈顶元素
while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
const top = stack.pop();
res[top] = i - top;
}
// 栈为空 或 每日温度小于等于栈顶温度 => 直接入栈
stack.push(i)
}
return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 543. 二叉树的直径
上一篇
评论
