企业官网建设流程全解析

LeetCode 739 Daily Temperatures 题解：单调栈求解"下一个更大元素"距离

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

导读

本文围绕 LeetCode 739「每日温度（Daily Temperatures）」展开，这是 leetcode 题解仓库「每日一题」系列活动在 2019-06-06 收录的经典题目，对应源码位于 daily/answers/739.daily-temperatures.js。题目要求对每一天的温度，计算需要等待多少天才能出现更高的温度，本质是"数组中每个元素之后第一个更大元素的距离"问题。读完本文你将掌握两种解法：O(n²) 暴力双层循环与 O(n) 单调递减栈，并理解单调栈这一算法范式如何在 42. 接雨水、84. 柱状图中最大的矩形 等同类问题中复用。

一、信息卡片与题目背景

该题在每日一题中的基础信息如下：

• 时间：2019-06-06
• 题目：739. Daily Temperatures
• tag：ArrayStack

仓库的 daily/README.md 中记录了每日一题的历史汇总，其中第 739 题的条目为tag: Array Stack，与本题核心算法（数组 + 栈）完全对应。每日一题是仓库作者在交流群中发起的共解一道题的活动，题目被记录后会筛选进入题解模块，因此本文所讲解的解法与仓库 problems 目录下的正式题解同源同质。

二、题目描述与约束分析

原题描述如下：

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

示例输入输出：

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

约束条件：

• 温度列表长度范围：[1, 30000]；
• 每个温度取值：[30, 100]。

题意拆解：对于下标i，需要找到最小的j > i使得T[j] > T[i]，答案记为j - i；若不存在这样的j，答案记为0。例如T[2] = 75，之后第一个大于 75 的是下标 6 的 76，等待天数为6 - 2 = 4。

需要特别注意的是等值不算更暖：只有严格大于（>）才满足条件，这一细节在编写比较条件时容易出错，也是两种解法的核心比较符。

三、解法一：暴力双层循环（O(n²)）

3.1 思路

最简单直观的做法：

1. 外层循环枚举"当天"T[i]，内层循环枚举"当天之后"的每一天T[j]（j从i+1开始）；
2. 一旦找到第一个满足T[j] > T[i]的j，则result[i] = j - i并跳出内层循环；
3. 若内层循环结束仍未找到，result[i]保持0。

原文档给出的 JavaScript 实现：

/** * @param {number[]} T * @return {number[]} * 双层for循环 */ var dailyTemperatures = function(T) { let result = []; for(let i = 0; i < T.length; i++) { result[i] = 0; for(let j = i + 1; j < T.length; j++) { if (T[i] < T[j]) { result[i] = j - i; break; } } } return result; };

3.2 复杂度与缺陷

• 时间复杂度：O(n²)。最坏情况下（如温度严格递减[100, 99, 98, ...]）每个i都要遍历完其后所有元素；
• 空间复杂度：O(1)，除结果数组外无额外空间。

原文档对该解法的评价是"效率很低"，这在 n 最大达 30000 时尤其明显——最坏约 9 亿次比较，在 LeetCode 上大概率超时。暴力解法价值在于帮助理解题意，作为优化解的对照基准。

四、解法二：单调递减栈（O(n)）

4.1 核心思想：栈中存下标

优化思路是用空间换时间：维护一个栈，栈内保存的是"尚未找到下一个更高温度"的下标。关键技巧在于栈中存下标而非温度值，因为答案要求天数差j - i，存下标才能同时取出温度（T[下标]）和计算距离。

维护单调性：从栈底到栈顶，下标对应的温度单调递减（即栈顶是当前已扫描温度中最低的"待处理"下标）。这正是 thinkings/monotone-stack.md 中定义的单调递减栈：以出栈顺序看，被弹出的元素按温度递减排列。

4.2 算法步骤

1. 初始化空栈stack和结果数组result（初始全部为 0）；
2. 从左到右for遍历数组，当前下标为i：
   • 若栈非空且T[stack 栈顶] < T[i]，说明当前温度T[i]就是栈顶下标之后第一个更高的温度，于是弹出栈顶peek，令result[peek] = i - peek；
   • 重复上一步，直到栈空或栈顶温度不小于T[i]（保持单调递减）；
   • 将i入栈；
3. 遍历结束后，栈中剩余的下标都是其后不存在更高温度的天，其result保持初始值0。

原文档给出的 JavaScript 实现：

/** * @param {number[]} T * @return {number[]} * 递减栈； */ var dailyTemperatures = function(T) { let stack = []; let result = []; for (let i = 0; i < T.length; i++) { result[i] = 0; while(stack.length > 0 && T[stack[stack.length - 1]] < T[i]) { let peek = stack.pop(); result[peek] = i - peek; } stack.push(i); } return result; };

Python3 实现：

class Solution: def dailyTemperatures(self, T: List[int]) -> List[int]: stack = [] ans = [0] * len(T) for i in range(len(T)): while stack and T[i] > T[stack[-1]]: peek = stack.pop(-1) ans[peek] = i - peek stack.append(i) return ans

4.3 逐步推演示例

以T = [73, 74, 75, 71, 69, 72, 76, 73]为例：

最终result = [1, 1, 4, 2, 1, 1, 0, 0]，与题目示例一致。可以看到，一个"暖锋"（如 76）经过时，会把栈中所有比它冷的天一次性结算掉，这正是单调栈高效的本质。

4.4 复杂度分析

• 时间复杂度：O(n)。每个下标最多入栈一次、出栈一次，均摊 O(1)，总代价线性；
• 空间复杂度：O(n)。栈最多同时容纳 n 个下标（例如温度严格递减时）。

仓库答案文件 daily/answers/739.daily-temperatures.js 同时保留了两种解法的实现：暴力版本被注释保留作为对比，正式采用单调栈版本，并标注了"典型的空间换时间"——这与本文的复杂度结论完全一致，可作为源码级佐证。

五、举一反三：单调栈通用模板

739. Daily Temperatures是 thinkings/monotone-stack.md 专题文章明确引用的代表题目（见其"题目推荐"一节）。该专题总结了如下通用模板，核心一句话是：如果压栈之后仍然可以保持单调性，直接压；否则先弹出栈内元素，直到压入后可以保持单调性。

Python 模板：

class Solution: def monostoneStack(self, arr: List[int]) -> List[int]: stack = [] ans = [0] * len(arr) # 初始值根据题意调整，可能是 -1 或 0 for i in range(len(arr)): while stack and arr[i] > arr[stack[-1]]: peek = stack.pop() ans[peek] = i - peek stack.append(i) return ans

JavaScript 模板：

var monostoneStack = function (T) { let stack = []; let result = []; for (let i = 0; i < T.length; i++) { result[i] = 0; while (stack.length > 0 && T[stack[stack.length - 1]] < T[i]) { let peek = stack.pop(); result[peek] = i - peek; } stack.push(i); } return result; };

5.1 模板的三个可调点

1. 比较符号：求解"下一个更大元素"用arr[i] > arr[栈顶]；求解"下一个更小元素"则反向。本题是找更高温度，故用>（Python 中对应T[i] > T[stack[-1]]）；
2. 答案赋值：本题存天数差i - peek；若题目要求存值（如下一个更大元素的值），则改为ans[peek] = arr[i]；
3. 初始值：本题不存在更高温度时填 0；若题目要求不存在时填 -1，则初始化数组为 -1，与 thinkings/monotone-stack.md 伪代码一致。

5.2 边界与哨兵法

原文档与单调栈专题均提醒：遍历结束后栈中残留的下标没有"下一个更大元素"。若题目需要利用到数组的全部信息，容易因忽略边界而漏解。专题推荐哨兵法：在原数组右侧追加一个足够小的值（如 -1），强制在遍历末尾把所有剩余元素弹出结算，从而简化代码逻辑。本题中残留元素答案天然为 0，无需额外处理，但理解这一技巧有助于应对其他变体。

六、单调栈相关题目推荐

掌握了 739 的单调栈解法后，可以在仓库中继续挑战以下同族题目，它们都依赖"下一个更大/更小元素"这一核心场景：

• 42. 接雨水：其"前置知识"明确列出单调栈，属于难度较大的应用；
• 84. 柱状图中最大的矩形：同样以单调栈为前置知识，寻找左右边界；
• 1019. 链表中的下一个更大节点：把数组换成链表，思路与本题高度同构，其题解原文明确指出"看完题目就应该想到单调栈"；
• thinkings/monotone-stack.md 还推荐了 316. 去除重复字母、402. 移掉 K 位数字、496. 下一个更大元素 I、581. 最短无序连续子数组、901. 股票价格跨度等题目。

七、总结

LeetCode 739「每日温度」是单调栈算法最典型的入门题之一：

1. 暴力解（双层循环，O(n²)）思路简单，适合理解题意，但在 n=30000 的约束下不可行；
2. 单调递减栈（O(n)）用"栈存下标、按温度单调"的方式，让每个元素只进出栈一次，以 O(n) 空间换取 O(n) 时间；
3. 解题关键三要素：栈中存下标而非值、比较用严格大于（等温不算更暖）、残留栈元素的答案保持为0；
4. 该题与仓库 thinkings/monotone-stack.md 专题、daily/answers/739.daily-temperatures.js 源码相互印证，可作为学习"下一个更大元素"问题族的最佳起点，后续可平滑过渡到接雨水、柱状图最大矩形、链表下一个更大节点等进阶题目。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode