【每日算法】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^530 <= 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⁵），需要高效求解 |
6. 总结
单调栈是解决“下一个更大元素”类问题的经典方法。它通过维护一个单调递减的栈，将寻找下一个更高温度的过程从暴力遍历的 O(n²) 优化到 O(n)。