739. 每日温度#

今天我们来聊一道热门题目 - LeetCode 739「每日温度」。这道题乍看简单，实则蕴含着单调栈这个强大工具的妙用。不用担心！我会用最通俗的语言，带你一步步掌握这个看似高深的数据结构。

📚 生活中的温度预测#

想象你是个天气预报员，手上有未来几天的温度预报。如果有人问：“从今天开始，要等几天才会遇到一个更暖和的天气？” 这就是我们今天要解决的问题！只不过我们要为每一天都回答这个问题。

问题描述#

题目目标#

给定一个整数数组 temperatures ，表示每天的温度。请返回一个数组 answer ，其中 answer[i] 表示在第 i 天之后，至少还需要等待多少天才能出现更高的气温；如果之后都不会升高，则该位置为 0。

示例 1#

输入： temperatures = [73,74,75,71,69,72,76,73] 输出： [1,1,4,2,1,1,0,0] 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

💡 问题是什么#

用大白话说就是：给你一串每天的温度数据，对于每一天，你要告诉我要往后等几天才能遇到一个更暖和的天气。如果后面都没有更暖和的天气，就记0天。

比如说：

输入温度：[73, 74, 75, 71, 69, 72, 76, 73]
输出等待天数：[1,  1,  4,  2,  1,  1,  0,  0]

java

我们一起分析第一个例子：

第1天是73度，第2天是74度，所以等1天就遇到更暖和的天气
第2天是74度，第3天是75度，也是等1天
第3天是75度，要等到第7天的76度才更暖和，所以等4天
以此类推…

🤔 怎么解决这个问题？#

1. 最简单的想法#

新手可能会想：对每一天，我都往后找一个比它暖和的天气。但这样做太费时间了，就像每次都要翻完整本日历才能找到答案。

2. 聪明的方法#

我们可以反过来想：与其一天天往后找，不如我们记住之前的天气，遇到暖和的天气时，就回头告诉之前在等待的日子们：“等待结束了！”

这就是单调栈的思路：它就像一个备忘录，记录着”正在等待更暖和天气”的日子。

🚀 写代码啦！#

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        // n 表示总天数，后续会频繁使用
        int n = temperatures.length;
        // answer[i] 记录第 i 天还要等几天才会出现更高温度，默认值 0
        int[] answer = new int[n];

        // 单调栈中存“下标”，不是温度值；栈内对应温度保持递减（从栈底到栈顶）
        Stack<Integer> stack = new Stack<>();

        // 从前到后扫描每一天
        for (int today = 0; today < n; today++) {
            // 当今天温度更高时，说明栈顶那些“在等更高温度”的天找到了答案
            while (!stack.isEmpty() && 
                   temperatures[today] > temperatures[stack.peek()]) {
                // 取出最晚一个仍未找到更高温度的日期
                int previousDay = stack.pop();
                // 等待天数 = 今天下标 - 当天下标
                answer[previousDay] = today - previousDay;
            }

            // 今天暂时还不知道未来哪天更暖，先入栈等待后续处理
            stack.push(today);
        }

        // 扫描结束后仍在栈中的日期，其后都没有更高温度，答案保持 0
        while (!stack.isEmpty()) {
            answer[stack.pop()] = 0;
        }

        // 返回每一天对应的等待天数
        return answer;
    }
}

java

📝 代码是怎么工作的？#

让我们用个具体的例子来看代码是怎么工作的。假设温度数据是：[73, 74, 75, 71, 69, 72, 76, 73]

第一天：73度
- 栈是空的
- 把第1天放入栈：[0]
第二天：74度
- 新温度74比栈顶（第1天的73）高
- 告诉第1天：等待1天
- 把第2天放入栈：[1]
第三天：75度
- 新温度75比栈顶（第2天的74）高
- 告诉第2天：等待1天
- 把第3天放入栈：[2]

以此类推…就像是在玩多米诺骨牌，一个温暖的天气可能会让好几个之前的日子都找到答案！

🎯 容易出错的地方#

栈里存什么？
- 存日期（数组下标），不是温度
- 因为我们需要计算等待天数
比较的是什么？
- 比较温度，但用的是日期找到温度
- temperatures[today] 和 temperatures[stack.peek()]
为什么要用栈？
- 栈能保持日期的顺序
- 新温度可能同时影响多个之前的日子

💡 举些生活中的例子#

这种思路在生活中很常见：

股票价格追踪
- 等待股票价格上涨
- 记录每个买入点要等多久才能盈利
排队买票
- 前面什么时候才会有空位
- 新开窗口时，很多人都能同时受益
等待公交车
- 下一班大容量公交车什么时候来
- 一辆大巴可能同时解决很多人的等待

🎨 图解演示#

<svg viewBox="0 0 800 400" xmlns="http://www.w3.org/2000/svg">
  <!-- 背景 -->
  <rect width="800" height="400" fill="#f8f9fa"/>

  <!-- 标题 -->
  <text x="50" y="40" font-size="20" fill="#1976d2">温度变化和等待天数</text>

  <!-- 温度曲线图 -->
  <g transform="translate(50,100)">
    <!-- 坐标轴 -->
    <line x1="0" y1="200" x2="600" y2="200" stroke="black"/>
    <line x1="0" y1="0" x2="0" y2="200" stroke="black"/>

    <!-- 温度折线 -->
    <path d="M 0 54 L 75 52 L 150 50 L 225 58 L 300 62 L 375 56 L 450 48 L 525 54" 
          fill="none" stroke="#e91e63" stroke-width="2"/>

    <!-- 数据点 -->
    <circle cx="0" cy="54" r="4" fill="#e91e63"/>
    <circle cx="75" cy="52" r="4" fill="#e91e63"/>
    <circle cx="150" cy="50" r="4" fill="#e91e63"/>
    <circle cx="225" cy="58" r="4" fill="#e91e63"/>
    <circle cx="300" cy="62" r="4" fill="#e91e63"/>
    <circle cx="375" cy="56" r="4" fill="#e91e63"/>
    <circle cx="450" cy="48" r="4" fill="#e91e63"/>
    <circle cx="525" cy="54" r="4" fill="#e91e63"/>

    <!-- 温度标签 -->
    <text x="0" y="44" text-anchor="middle">73°</text>
    <text x="75" y="42" text-anchor="middle">74°</text>
    <text x="150" y="40" text-anchor="middle">75°</text>
    <text x="225" y="48" text-anchor="middle">71°</text>
    <text x="300" y="52" text-anchor="middle">69°</text>
    <text x="375" y="46" text-anchor="middle">72°</text>
    <text x="450" y="38" text-anchor="middle">76°</text>
    <text x="525" y="44" text-anchor="middle">73°</text>
  </g>

  <!-- 等待天数说明 -->
  <g transform="translate(50,350)">
    <text x="0" y="0" font-size="14">等待天数：</text>
    <text x="0" y="20" font-size="14">[1, 1, 4, 2, 1, 1, 0, 0]</text>
  </g>
</svg>

plaintext

🌟 面试时怎么说？#

先说思路
- “我们可以用单调栈来记录正在等待更暖和天气的日子”
- “新来一个温度时，就看看能不能解决之前日子的等待”
解释选择
- 为什么不用简单方法：会重复太多次查找
- 为什么选择单调栈：一次遍历就能解决所有等待
补充说明
- 时间复杂度是O(n)：每个元素最多进出栈一次
- 空间复杂度是O(n)：最坏情况下温度递减，所有天数都在栈中

🎩 更多玩法#

我们还可以用这个思路解决类似的问题：

找下一个更大的数

// 与每日温度相同：都用单调栈维护“还没找到更大值”的位置
public int[] nextGreaterElement(int[] nums) {
    // 核心差异只在比较条件与返回语义，其余流程基本一致
}

java

股票跨度问题

// 同样是单调结构：维护价格序列，快速得到连续满足条件的区间长度
class StockSpanner {
    // 每次新价格到来时，弹出不再需要的历史数据并累计跨度
}

java

记住：单调栈就像是一个”等待室”，当新来的元素满足条件时，就可以解决之前元素的等待问题。这个思路在很多地方都能用到！

这道题看似简单，实则暗藏玄机。通过单调栈这个工具，我们可以优雅地解决很多看似需要大量查找的问题。如果你对这个话题还有任何疑问，欢迎在评论区讨论！