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 TemperaturestagArrayStack仓库的 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 思路最简单直观的做法外层循环枚举当天T[i]内层循环枚举当天之后的每一天T[j]j从i1开始一旦找到第一个满足T[j] T[i]的j则result[i] j - i并跳出内层循环若内层循环结束仍未找到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 算法步骤初始化空栈stack和结果数组result初始全部为 0从左到右for遍历数组当前下标为i若栈非空且T[stack 栈顶] T[i]说明当前温度T[i]就是栈顶下标之后第一个更高的温度于是弹出栈顶peek令result[peek] i - peek重复上一步直到栈空或栈顶温度不小于T[i]保持单调递减将i入栈遍历结束后栈中剩余的下标都是其后不存在更高温度的天其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 ans4.3 逐步推演示例以T [73, 74, 75, 71, 69, 72, 76, 73]为例iT[i]操作栈存下标结果变化073入栈[0]result 全 0174T[0]73 74弹出 0result[0]1-01入栈 1[1]result[0]1275T[1]74 75弹出 1result[1]1入栈 2[2]result[1]137171 不大于 75直接入栈[2,3]-46969 不大于 71直接入栈[2,3,4]-572T[4]69 72弹出 4result[4]1T[3]71 72弹出 3result[3]2入栈 5[2,5]result[4]1, result[3]2676T[5]72 76弹出 5result[5]1T[2]75 76弹出 2result[2]4入栈 6[6]result[5]1, result[2]477373 不大于 76入栈[6,7]-最终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 ansJavaScript 模板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 模板的三个可调点比较符号求解下一个更大元素用arr[i] arr[栈顶]求解下一个更小元素则反向。本题是找更高温度故用Python 中对应T[i] T[stack[-1]]答案赋值本题存天数差i - peek若题目要求存值如下一个更大元素的值则改为ans[peek] arr[i]初始值本题不存在更高温度时填 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「每日温度」是单调栈算法最典型的入门题之一暴力解双层循环O(n²)思路简单适合理解题意但在 n30000 的约束下不可行单调递减栈O(n)用栈存下标、按温度单调的方式让每个元素只进出栈一次以 O(n) 空间换取 O(n) 时间解题关键三要素栈中存下标而非值、比较用严格大于等温不算更暖、残留栈元素的答案保持为0该题与仓库 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考