【每日算法】LeetCode 739. 每日温度：从暴力遍历到单调栈的优雅解决-育师

对前端开发者而言，学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

LeetCode 739. 每日温度：从暴力遍历到单调栈的优雅解决

1. 题目描述

给定一个整数数组temperatures，表示每天的温度，返回一个数组answer，其中answer[i]是指对于第i天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用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 <= 10^5
30 <= temperatures[i] <= 100

2. 问题分析

这道题本质上是在寻找每个元素右侧第一个比它大的元素，并计算两者之间的索引距离。在前端开发中，类似的问题场景很多，例如：

在时间轴组件中，寻找下一个热度更高的事件点。
在股票价格图表中，计算下一次价格超过当前价格所需的天数。
在构建响应式布局时，可能需要根据元素宽度找到下一个更宽的断点。

由于数据规模可达10^5，简单的O(n^2)暴力解法会超时，因此必须寻找更优的O(n)或O(n log n)解法。

3. 解题思路

3.1 暴力法（双层循环）

对于每个元素，向后遍历直到找到第一个比它大的元素，计算索引差。这种方法直观但效率低下。

复杂度分析：

时间复杂度：O(n²)，在最坏情况下（如单调递减数组）需要比较 n*(n-1)/2 次。
空间复杂度：O(1)，除了结果数组外，没有使用额外的空间。

3.2 单调栈法（最优解）

维护一个存储下标的栈，栈中的下标对应的温度是单调递减的。遍历数组，当当前温度大于栈顶下标对应的温度时，说明当前温度是栈顶下标的下一个更高温度，于是弹出栈顶，计算索引差，并将结果存入答案数组。重复此过程直到栈为空或当前温度不大于栈顶温度，然后将当前下标入栈。

复杂度分析：

时间复杂度：O(n)，每个元素最多入栈和出栈一次。
空间复杂度：O(n)，最坏情况下栈的大小为 n。

4. 各思路代码实现

4.1 暴力法代码实现

/** * @param {number[]} temperatures * @return {number[]} */vardailyTemperatures=function(temperatures){constn=temperatures.length;constanswer=newArray(n).fill(0);for(leti=0;i<n;i++){for(letj=i+1;j<n;j++){if(temperatures[j]>temperatures[i]){answer[i]=j-i;break;}}}returnanswer;};

4.2 单调栈法代码实现

/** * @param {number[]} temperatures * @return {number[]} */vardailyTemperatures=function(temperatures){constn=temperatures.length;constanswer=newArray(n).fill(0);conststack=[];// 存储下标，栈底到栈顶对应的温度递减for(leti=0;i<n;i++){// 当栈不为空且当前温度大于栈顶下标对应的温度时while(stack.length&&temperatures[i]>temperatures[stack[stack.length-1]]){constidx=stack.pop();answer[idx]=i-idx;}stack.push(i);}returnanswer;};

单调栈法的过程示例（以 temperatures = [73,74,75,71,69,72,76,73] 为例）：

步骤	当前索引 i	当前温度	栈 (下标)	操作	answer 更新
1	0	73	[]	栈空，0入栈	[]
2	1	74	[0]	74 > 73，弹出0，answer[0]=1-0=1，然后1入栈	[1,0,0,0,0,0,0,0]
3	2	75	[1]	75 > 74，弹出1，answer[1]=2-1=1，然后2入栈	[1,1,0,0,0,0,0,0]
4	3	71	[2]	71 <= 75，3入栈	[1,1,0,0,0,0,0,0]
5	4	69	[2,3]	69 <= 71，4入栈	[1,1,0,0,0,0,0,0]
6	5	72	[2,3,4]	72 > 69，弹出4，answer[4]=5-4=1；72 > 71，弹出3，answer[3]=5-3=2；72 <= 75，停止，5入栈	[1,1,0,2,1,0,0,0]
7	6	76	[2,5]	76 > 72，弹出5，answer[5]=6-5=1；76 > 75，弹出2，answer[2]=6-2=4；栈空，6入栈	[1,1,4,2,1,1,0,0]
8	7	73	[6]	73 <= 76，7入栈	[1,1,4,2,1,1,0,0]
结束	-	-	[6,7]	栈中剩余元素对应 answer 为 0（已初始化）	[1,1,4,2,1,1,0,0]

5. 各实现思路的复杂度、优缺点对比表格

方法	时间复杂度	空间复杂度	优点	缺点	适用场景
暴力法	O(n²)	O(1)	实现简单，易于理解	效率低，在数据量大时无法通过	数据规模较小（n ≤ 10³）或快速原型验证
单调栈法	O(n)	O(n)	效率高，线性时间解决	需要理解栈的单调性，相对抽象	数据规模大（n ≤ 10⁵），需要高效求解