LeetCode 739 Daily Temperatures从暴力到单调栈与 DP 跳转的下一更大元素全解leetcode 仓库版【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文基于 leetcode 开源仓库中的 daily-temperatures 解题文档 展开围绕第 739 题「Daily Temperatures每日温度」讲解三种递进式解法双重循环暴力、单调栈、逆序动态规划跳转覆盖每种方法的直觉、完整算法步骤与多语言实现代码并结合仓库中 python/0739-daily-temperatures.py、rust/0739-daily-temperatures.rs、c/0739-daily-temperatures.c 等真实实现文件交叉印证。读完后你既能掌握下一个更大元素Next Greater Element这一经典单调栈问题的完整解法体系也能明确每种方案的时间/空间复杂度与典型错误陷阱。问题背景与前置知识题目要求给定一个整数数组temperatures表示每天的温度返回一个等长数组res其中res[i]表示第i天之后需要再等多少天才能迎来更高温度若之后一直没有更热的一天则res[i] 0。文档中给出的经典样例temperatures [73,74,75,71,69,72,76,73] res [1,1,4,2,1,1,0,0]在动手之前文档列出了三个前置知识要求单调栈Monotonic Stack使用保持元素递增或递减顺序的栈来高效地寻找下一个更大元素。这是本题第二解法的核心数据结构。数组遍历Array Traversal既会正向也会逆向遍历数组来计算结果DP 解法依赖从右向左的遍历。基础动态规划Dynamic Programming, Basic复用之前已经算好的结果跳过不必要的比较这正是第三解法跳转思想的来源。从源码结构看本题在仓库中属于 LeetCode 739 题仓库以0739-daily-temperatures.ext的命名方式在 12 种语言目录下各维护了一份实现C、C、C#、Go、Java、JavaScript、Kotlin、Python、Ruby、Rust、Swift、TypeScriptREADME.md 的完成度表格中也收录了该题条目。解法一暴力扫描Brute Force直觉对每一天直接向后逐个查看直到找到第一天气温更高的一天或扫到数组末尾。若找到了记录等待的天数否则答案为0。这种方法最容易理解但慢在每一天都可能向后扫描很多天。算法步骤令res存储等到更热的一天所需的天数。对每个下标i从第二天j i 1开始检查统计找到更热的一天走了多少步若找到更热的一天存入计数否则存入0。返回结果数组。各语言实现Pythonclass Solution: def dailyTemperatures(self, temperatures: List[int]) - List[int]: n len(temperatures) res [] for i in range(n): count 1 j i 1 while j n: if temperatures[j] temperatures[i]: break j 1 count 1 count 0 if j n else count res.append(count) return resJavapublic class Solution { public int[] dailyTemperatures(int[] temperatures) { int n temperatures.length; int[] res new int[n]; for (int i 0; i n; i) { int count 1; int j i 1; while (j n) { if (temperatures[j] temperatures[i]) { break; } j; count; } count (j n) ? 0 : count; res[i] count; } return res; } }Cclass Solution { public: vectorint dailyTemperatures(vectorint temperatures) { int n temperatures.size(); vectorint res(n); for (int i 0; i n; i) { int count 1; int j i 1; while (j n) { if (temperatures[j] temperatures[i]) { break; } j; count; } count (j n) ? 0 : count; res[i] count; } return res; } };JavaScriptclass Solution { /** * param {number[]} temperatures * return {number[]} */ dailyTemperatures(temperatures) { const n temperatures.length; const res new Array(n).fill(0); for (let i 0; i n; i) { let count 1; let j i 1; while (j n) { if (temperatures[j] temperatures[i]) { break; } j; count; } count j n ? 0 : count; res[i] count; } return res; } }C#public class Solution { public int[] DailyTemperatures(int[] temperatures) { int n temperatures.Length; int[] res new int[n]; for (int i 0; i n; i) { int count 1; int j i 1; while (j n) { if (temperatures[j] temperatures[i]) { break; } j; count; } count (j n) ? 0 : count; res[i] count; } return res; } }Gofunc dailyTemperatures(temperatures []int) []int { n : len(temperatures) res : make([]int, 0) for i : 0; i n; i { count : 1 j : i 1 for j n { if temperatures[j] temperatures[i] { break } j count } if j n { count 0 } res append(res, count) } return res }Kotlinclass Solution { fun dailyTemperatures(temperatures: IntArray): IntArray { val n temperatures.size val res mutableListOfInt() for (i in 0 until n) { var count 1 var j i 1 while (j n) { if (temperatures[j] temperatures[i]) { break } j count } count if (j n) 0 else count res.add(count) } return res.toIntArray() } }Swiftclass Solution { func dailyTemperatures(_ temperatures: [Int]) - [Int] { let n temperatures.count var res [Int]() for i in 0..n { var count 1 var j i 1 while j n { if temperatures[j] temperatures[i] { break } j 1 count 1 } count (j n) ? 0 : count res.append(count) } return res } }Rustimpl Solution { pub fn daily_temperatures(temperatures: Veci32) - Veci32 { let n temperatures.len(); let mut res vec![0; n]; for i in 0..n { let mut count 1; let mut j i 1; while j n { if temperatures[j] temperatures[i] { break; } j 1; count 1; } res[i] if j n { 0 } else { count }; } res } }时间与空间复杂度时间复杂度$O(n^2)$ —— 最坏情况下如温度单调不升每一天都要扫描到末尾。空间复杂度额外 $O(1)$ 空间不计输出数组输出数组 $O(n)$。暴力解的价值在于作为正确性参照任何优化解法的输出都必须与它一致。在数据规模较小或只需原型实现时可以直接使用。解法二单调栈Stack—— 仓库的主力解法直觉我们希望知道每天之后多久会出现更热的一天。栈在这里的作用是追踪所有还在等待更热一天的日子。正向扫描时只要发现当前温度比栈顶的温度高就说明刚找到了那个更早的日子的下一更热日弹出栈顶、计算天数差、继续检查新的栈顶直到栈顶温度不低于当前温度为止。这样每个日子最多入栈一次、出栈一次整个处理过程因此高效。算法步骤创建一个全零的结果数组。使用栈存储 (temperature, index) 对代表尚未找到更热一天的日子。顺序遍历温度数组当栈非空且当前温度严格大于栈顶温度时弹出栈顶计算两个下标之差并写入结果将当前日子 (t, i) 压入栈。返回填好的结果数组。各语言实现Pythonclass Solution: def dailyTemperatures(self, temperatures: List[int]) - List[int]: res [0] * len(temperatures) stack [] # pair: [temp, index] for i, t in enumerate(temperatures): while stack and t stack[-1][0]: stackT, stackInd stack.pop() res[stackInd] i - stackInd stack.append((t, i)) return resJavapublic class Solution { public int[] dailyTemperatures(int[] temperatures) { int[] res new int[temperatures.length]; Stackint[] stack new Stack(); // pair: [temp, index] for (int i 0; i temperatures.length; i) { int t temperatures[i]; while (!stack.isEmpty() t stack.peek()[0]) { int[] pair stack.pop(); res[pair[1]] i - pair[1]; } stack.push(new int[]{t, i}); } return res; } }Cclass Solution { public: vectorint dailyTemperatures(vectorint temperatures) { vectorint res(temperatures.size(), 0); stackpairint, int stack; // pair: {temp, index} for (int i 0; i temperatures.size(); i) { int t temperatures[i]; while (!stack.empty() t stack.top().first) { auto pair stack.top(); stack.pop(); res[pair.second] i - pair.second; } stack.push({t, i}); } return res; } };JavaScriptclass Solution { /** * param {number[]} temperatures * return {number[]} */ dailyTemperatures(temperatures) { const res new Array(temperatures.length).fill(0); const stack []; // pair: [temp, index] for (let i 0; i temperatures.length; i) { const t temperatures[i]; while (stack.length 0 t stack[stack.length - 1][0]) { const [stackT, stackInd] stack.pop(); res[stackInd] i - stackInd; } stack.push([t, i]); } return res; } }C#public class Solution { public int[] DailyTemperatures(int[] temperatures) { int[] res new int[temperatures.Length]; Stackint[] stack new Stackint[](); // pair: [temp, index] for (int i 0; i temperatures.Length; i) { int t temperatures[i]; while (stack.Count 0 t stack.Peek()[0]) { int[] pair stack.Pop(); res[pair[1]] i - pair[1]; } stack.Push(new int[] { t, i }); } return res; } }Gofunc dailyTemperatures(temperatures []int) []int { res : make([]int, len(temperatures)) stack : []int{} for i, t : range temperatures { for len(stack) 0 t temperatures[stack[len(stack)-1]] { stackInd : stack[len(stack)-1] stack stack[:len(stack)-1] res[stackInd] i - stackInd } stack append(stack, i) } return res }Kotlinclass Solution { fun dailyTemperatures(temperatures: IntArray): IntArray { val res IntArray(temperatures.size) { 0 } val stack mutableListOfInt() for (i in temperatures.indices) { while (stack.isNotEmpty() temperatures[i] temperatures[stack.last()]) { val stackInd stack.removeAt(stack.size - 1) res[stackInd] i - stackInd } stack.add(i) } return res } }Swiftclass Solution { func dailyTemperatures(_ temperatures: [Int]) - [Int] { var res Int var stack [(Int, Int)]() // Pair: (temperature, index) for (i, t) in temperatures.enumerated() { while !stack.isEmpty t stack.last!.0 { let (stackT, stackInd) stack.removeLast() res[stackInd] i - stackInd } stack.append((t, i)) } return res } }Rustimpl Solution { pub fn daily_temperatures(temperatures: Veci32) - Veci32 { let mut res vec![0i32; temperatures.len()]; let mut stack: Vec(i32, usize) Vec::new(); for (i, t) in temperatures.iter().enumerate() { while let Some((top_t, top_i)) stack.last() { if t top_t { stack.pop(); res[top_i] (i - top_i) as i32; } else { break; } } stack.push((t, i)); } res } }时间与空间复杂度时间复杂度$O(n)$空间复杂度$O(n)$结果数组 栈最坏情况可存满 n 个元素为什么是 O(n)每个日子最多进出栈各一次时间线性可以从源码结构上严格说明外层for循环共执行 n 次内层while的每一次迭代都必然伴随一次pop而每个下标在整个过程中至多入栈一次、出栈一次因此所有while迭代次数总和不超过 n总操作量为 $O(n n) O(n)$。这个摊还分析是所有单调栈线性解法的通用论证。仓库源码印证仓库中的多语言实现与该解法一一对应可以逐一验证python/0739-daily-temperatures.py与文档的 Python 栈解法逐行一致——用(t, i)元组入栈while stack and t stack[-1][0]弹出并写res[stackInd] i - stackInd。rust/0739-daily-temperatures.rsRust 版同样维护Vec(i32, usize)作为栈while !stack.is_empty() *val stack.last().unwrap().0的条件与文档的严格大于判断一致并展示了所有权/引用解包(*val, i)压栈的惯用写法。javascript/0739-daily-temperatures.js该文件收录了三个版本——第一个版本只存下标、通过temp[stack[stack.length - 1]]间接取温度比文档的元组版本更省空间第二个版本把能否收缩的判断抽成canShrink辅助函数语义为prevTemperature currTemperature即严格小于是同一思想的函数式改写。这印证了文档中只存下标也能工作的提示见后文陷阱第二节。文件头部注释也标注了Time O(N) | Space O(N)与文档的复杂度结论一致。栈解法有一个值得注意的特性它是在线online的——只从左到右扫描一遍不需要预知数组后面的内容适合流式数据场景而下面的 DP 解法必须从右向左扫描依赖右侧已算好的结果。解法三动态规划跳转逆序 跳跃直觉不必逐天检查每一个未来日子可以复用之前算好的答案。如果第j天不比第i天更热就不必一步步向前走——可以直接利用为第j天已经算好的结果做跳转。这样能跳过大量不必要的比较。从右向左处理并借助这些跳转即可高效地为每个位置找到下一更热日。算法步骤创建一个全零的结果数组res。从右向左遍历温度数组i从n-2递减到0。对每一天i从下一天j i 1开始当j在界内且temperatures[j] temperatures[i]时若res[j] 0说明j之后没有更热的一天 → 停止j n否则向前跳res[j]天即j res[j]若最终j仍在界内说明temperatures[j] temperatures[i]置res[i] j - i。返回res。跳转的正确性依据若temperatures[j] temperatures[i]那么比j还热的一天如果存在一定落在j res[j]处所以可以直接跳到那个位置继续比较中间的所有天都不必再看。各语言实现Pythonclass Solution: def dailyTemperatures(self, temperatures: List[int]) - List[int]: n len(temperatures) res [0] * n for i in range(n - 2, -1, -1): j i 1 while j n and temperatures[j] temperatures[i]: if res[j] 0: j n break j res[j] if j n: res[i] j - i return resJavapublic class Solution { public int[] dailyTemperatures(int[] temperatures) { int n temperatures.length; int[] res new int[n]; for (int i n - 2; i 0; i--) { int j i 1; while (j n temperatures[j] temperatures[i]) { if (res[j] 0) { j n; break; } j res[j]; } if (j n) { res[i] j - i; } } return res; } }Cclass Solution { public: vectorint dailyTemperatures(vectorint temperatures) { int n temperatures.size(); vectorint res(n, 0); for (int i n - 2; i 0; i--) { int j i 1; while (j n temperatures[j] temperatures[i]) { if (res[j] 0) { j n; break; } j res[j]; } if (j n) { res[i] j - i; } } return res; } };JavaScriptclass Solution { /** * param {number[]} temperatures * return {number[]} */ dailyTemperatures(temperatures) { const n temperatures.length; const res new Array(n).fill(0); for (let i n - 2; i 0; i--) { let j i 1; while (j n temperatures[j] temperatures[i]) { if (res[j] 0) { j n; break; } j res[j]; } if (j n) { res[i] j - i; } } return res; } }C#public class Solution { public int[] DailyTemperatures(int[] temperatures) { int n temperatures.Length; int[] res new int[n]; for (int i n - 2; i 0; i--) { int j i 1; while (j n temperatures[j] temperatures[i]) { if (res[j] 0) { j n; break; } j res[j]; } if (j n) { res[i] j - i; } } return res; } }Gofunc dailyTemperatures(temperatures []int) []int { n : len(temperatures) res : make([]int, n) for i : n - 2; i 0; i-- { j : i 1 for j n temperatures[j] temperatures[i] { if res[j] 0 { j n break } j res[j] } if j n { res[i] j - i } } return res }Kotlinclass Solution { fun dailyTemperatures(temperatures: IntArray): IntArray { val n temperatures.size val res IntArray(n) for (i in n - 2 downTo 0) { var j i 1 while (j n temperatures[j] temperatures[i]) { if (res[j] 0) { j n break } j res[j] } if (j n) { res[i] j - i } } return res } }Swiftclass Solution { func dailyTemperatures(_ temperatures: [Int]) - [Int] { let n temperatures.count var res Int for i in stride(from: n - 2, through: 0, by: -1) { var j i 1 while j n temperatures[j] temperatures[i] { if res[j] 0 { j n break } j res[j] } if j n { res[i] j - i } } return res } }Rustimpl Solution { pub fn daily_temperatures(temperatures: Veci32) - Veci32 { let n temperatures.len(); let mut res vec![0i32; temperatures.len()]; for i in (0..n.saturating_sub(1)).rev() { let mut j i 1; while j n temperatures[j] temperatures[i] { if res[j] 0 { j n; break; } j res[j] as usize; } if j n { res[i] (j - i) as i32; } } res } }时间与空间复杂度时间复杂度$O(n)$空间复杂度额外 $O(1)$ 空间不计输出数组输出数组 $O(n)$关于 $O(n)$ 的说明虽然代码里有双层循环但可以从源码结构上论证其摊还线性——逆序处理时内层while的每次j res[j]跳转都会使j严格越过若干个位置且对于每个i被跳过的区间的res值之和即j - (i1)恰等于其结果res[i]所有i的res[i]之和不超过 $n^2/2$ 这一上界并不直接给出线性结论实践中该解法与栈解法一样在典型温度序列上表现接近线性面试/工程中以栈解法作为复杂度论证更严谨的标准答案。文档将其标注为 $O(n)$这里如实继承并提示跳转解法的严格复杂度依赖输入分布这一前提。仓库源码印证C 语言实现正是这一解法c/0739-daily-temperatures.c仓库的 C 实现采用的正是从右向左 j result[j]跳转的 DP 解法for (int i temperaturesSize-1; i 0; --i)与文档第三解法完全同构并在文件头注释中给出了示例temperatures [73,74,75,71,69,72,76,73] - [1,1,4,2,1,1,0,0]和Time: O(N)的标注。C 版本中有一个值得注意的细节它用if (result[j] 0) break;而非 0判断无更热日由于结果恒非负两者等价体现了 C 中对边界防御的保守写法。javascript/0739-daily-temperatures.js 的第三个版本也是 DP 跳转思想的变体逆序扫描、用hottest记录从尾部看过的最高温做剪枝再用递归search沿days[day dayCount]跳转寻找更热日。从源码结构看这是把跳转从迭代改写为递归的实现与文档给出的迭代版逻辑等价。三种解法对比维度暴力扫描单调栈DP 跳转时间复杂度$O(n^2)$$O(n)$$O(n)$摊还额外空间$O(1)$$O(n)$栈$O(1)$遍历方向正向内层向后扫描正向一遍扫描逆向一遍扫描是否在线是是否依赖右侧结果仓库代表文件—文档给出多语言版本python/0739-daily-temperatures.py、rust/0739-daily-temperatures.rs、javascript/0739-daily-temperatures.jsc/0739-daily-temperatures.c选型建议面试首选单调栈——$O(n)$ 时间、论证严谨、且能推广到一切下一个更大/更小元素问题空间敏感且允许一次逆序遍历时可选 DP 跳转仅比栈解法多占 $O(1)$ 额外空间暴力解仅用于小规模数据或作为正确性基准。常见陷阱Common Pitfalls文档专门总结了三个高频错误逐一继承如下。陷阱一用大于等于替代严格大于题目要求的是下一更热的一天即严格大于。把条件写成会让算法在温度相等时提前停止或提前弹出产生错误结果。# Wrong: stops at equal temperatures while stack and t stack[-1][0]: # This pops when temperatures are equal, not just warmer # Correct: strictly greater while stack and t stack[-1][0]: stackT, stackInd stack.pop() res[stackInd] i - stackInd对照仓库源码python/0739-daily-temperatures.py 与 rust/0739-daily-temperatures.rs 中的判断均为严格javascript/0739-daily-temperatures.js 中canShrink使用的也是prevTemperature currTemperature严格小于三处实现与该严格语义保持一致。陷阱二栈中只存下标时温度访问方式混淆用栈时需要比较温度。只存下标本身没问题——只要能通过temperatures[index]取到温度即可但若把下标和值混用比如比较stack[-1]这个下标本身与温度值就会得到错误结果。文档给出的正确写法# Correct: store just indices but access temperature via array stack [] # stores indices for i, t in enumerate(temperatures): while stack and t temperatures[stack[-1]]: idx stack.pop() res[idx] i - idx stack.append(i)这正是仓库 javascript/0739-daily-temperatures.js 第一个版本的做法stack只存i比较时通过temp[stack[stack.length - 1]]间接取温度比元组方案少存一份温度值。陷阱三等待天数的 off-by-one 错误结果应当是需要等待的天数即两个下标之差。若从 0 开始手工累加count很容易把计数起点弄错、差出一天。文档给出的对比# Wrong: starting count at 0 count 0 j i 1 while j n and temperatures[j] temperatures[i]: j 1 count 1 # count is now j - i - 1, off by one # Correct: difference of indices res[i] j - i # Direct index difference gives correct wait days要点凡是涉及等了多少天的题目直接用下标差j - i计算避免手工维护计数器。小结围绕 articles/daily-temperatures.md 这条主线本文完整覆盖了三种解法的直觉、步骤与 9 语言代码暴力 $O(n^2)$ 给出正确性基线单调栈 $O(n)$ 凭借每个日子最多进出栈一次成为标准答案且仓库中 Python、Rust、JavaScript 等实现均以此为主力写法DP 跳转用逆序遍历加j res[j]复用既有结果以 $O(1)$ 额外空间达到摊还线性仓库的 C 实现 正是该路线的代表。再配合严格大于、下标与值分离、下标差算天数三条避坑准则即可在 LeetCode 739 及其同族下一更大元素题目上稳定输出正确且高效的解法。如需继续深入可在仓库中按0739-daily-temperatures.*的命名规则查看 C、C、C#、Go、Java、Kotlin、Python、Ruby、Rust、Swift、TypeScript 等 12 种语言的完整实现。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考