LeetCode - 739.每日温度问题单调栈解法

2025/4/9 1:31:28 来源：https://blog.csdn.net/qq_63358859/article/details/147009967 浏览: 次关键词：LeetCode - 739.每日温度问题单调栈解法

问题描述

方法思路：单调栈

核心思想

为什么用单调栈？

算法步骤

代码实现与逐行解析

示例解析

复杂度分析

总结

问题描述

给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 表示在第 i 天之后，需要等待多少天才能遇到更高的温度。若未来没有更高温度，则 answer[i] = 0。

示例：

输入：temperatures = [73,74,75,71,69,72,76,73]
输出：[1,1,4,2,1,1,0,0]

第 0 天温度为 73，第 1 天温度为 74，因此只需等待 1 天；第 6 天温度为 76，后续没有更高温度，结果为 0。

方法思路：单调栈

核心思想

利用单调递减栈存储尚未找到更高温度的日期索引。栈中元素对应的温度从栈底到栈顶严格递减。遍历温度数组时，若当前温度高于栈顶温度，则栈顶元素找到了下一个更高温度的日期，计算天数差并更新结果，确保栈的单调性。

为什么用单调栈？

暴力法的不足：对每一天向后遍历找更高温度，时间复杂度为 O(n²)，无法处理大规模数据。
单调栈的优势：每个元素最多入栈和出栈一次，时间复杂度优化至 O(n)。

算法步骤

初始化：结果数组 ans 初始化为全 0，栈 stack 存储索引。
遍历温度数组：对于第 i 天的温度 T[i]：
- 循环检查栈顶：若 T[i] > T[栈顶索引]，说明栈顶元素的下一个更高温度是第 i 天：
- 弹出栈顶索引 prevIndex，计算 ans[prevIndex] = i - prevIndex。
- 维护单调性：将 i 压入栈，保持栈内温度递减。
返回结果：遍历结束后，ans 数组即为所求。

代码实现与逐行解析

var dailyTemperatures = function (temperatures) {const n = temperatures.length;const ans = new Array(n).fill(0); // 初始化结果数组为全0const stack = []; // 单调栈存储索引，栈底到栈顶温度递减for (let i = 0; i < n; i++) {// 当前温度 > 栈顶温度时，循环处理栈顶元素while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {const prevIndex = stack.pop(); // 弹出栈顶索引ans[prevIndex] = i - prevIndex; // 计算天数差}stack.push(i); // 当前索引入栈，保持栈的单调性}return ans;
};

初始化结果数组：ans 初始化为全 0，默认未来没有更高温度时结果为 0。

遍历温度数组：对每一天的温度进行处理。

循环处理栈顶元素：当栈不为空且当前温度高于栈顶温度时：

弹出栈顶索引：获取需要更新结果的日期 prevIndex。

计算等待天数：结果为当前日期 i 与 prevIndex 的差值。

压入当前索引：确保栈内温度保持递减。

示例解析

以 temperatures = [73,74,75,71,69,72,76,73] 为例，逐步分析栈和结果的变化：

当前索引 `i`	当前温度 `T[i]`	栈状态 (索引)	操作	结果数组 `ans`
0	73	[]	0入栈	[0,0,0,0,0,0,0,0]
1	74	[0]	73 < 74 → 计算ans[0]=1，0出栈，1入栈	[1,0,0,0,0,0,0,0]
2	75	[1]	74 < 75 → 计算ans[1]=1，1出栈，2入栈	[1,1,0,0,0,0,0,0]
3	71	[2]	75 > 71 → 3入栈	无变化
4	69	[2,3]	71 > 69 → 4入栈	无变化
5	72	[2,3,4]	69 < 72 → 计算ans[4]=1，4出栈；71 <72 → 计算ans[3]=2，3出栈；75 >72 → 5入栈	[1,1,0,2,1,0,0,0]
6	76	[2,5]	72 <76 → 计算ans[5]=1，5出栈；75 <76 → 计算ans[2]=4，2出栈；栈空 → 6入栈	[1,1,4,2,1,1,0,0]
7	73	[6]	76 >73 → 7入栈	无变化