你好，同学。很高兴能和你一起探讨这道经典的算法题。在 NOI 竞赛中，这类涉及到“寻找侧边第一个大于/小于值”的问题是非常基础且重要的。

【题目描述】每日温度 (Daily Temperatures)

题目背景： 在气象数据分析中，寻找气温上升的周期是一个重要的任务。给定一组历史温度数据，我们需要计算对于每一天，还需要等待多少天才能等到一个更暖和的气温。

问题描述： 给定一个长度为 $n$ 的整数数组 $T$，表示每日的气温。请输出一个数组 $ans$，其中 $ans[i]$ 是指对于第 $i$ 天，下一个气温比第 $i$ 天高的日期距离第 $i$ 天的天数。如果之后都没有更高气温，则 $ans[i] = 0$。

输入格式： 第一行包含一个整数 $n$，表示总天数。 第二行包含 $n$ 个整数，表示每日的气温 $T_i$。

输出格式： 输出一行 $n$ 个整数，用空格隔开，对应每天的等待天数。

样例输入：

8
73 74 75 71 69 72 76 73

样例输出：

1 1 4 2 1 1 0 0

数据范围： 对于 $100\%$ 的数据：$1 \le n \le 10^5$，$30 \le T_i \le 100$。 内存限制：256MB，时间限制：1s。

一、 预备知识点

1. 栈 (Stack)：先进后出的线性数据结构。
2. 单调栈 (Monotonic Stack)：栈内元素保持单调递增或单调递减的特殊用法。
3. 时间复杂度分析：如何通过空间换时间，将 $O(n^2)$ 优化至 $O(n)$。

二、 启发式教学：草稿纸上的推演

现在，请拿出你的草稿纸，我们不直接写代码，而是模拟大脑思考的过程。

1. 暴力直觉 (Brute Force)

最容易想到的是：对于每一天 $i$，向后扫描 $j = i+1, i+2...$ 直到找到第一个 $T[j] > T[i]$。

• 复杂度：最坏情况下（如温度递减），时间复杂度为 $O(n^2)$。
• 瓶颈：当 $n=10^5$ 时，$n^2 = 10^{10}$，显然会超时（TLE）。我们需要一种“一次遍历”就能记录信息的办法。

2. 逆向思考与信息保存

当我们遍历到某一天时，如果还没找到比它暖和的天，这一天就处于“等待状态”。

• 观察：如果今天比昨天暖和，那么昨天的等待就结束了。
• 工具选择：我们需要存储“还没找到更高温的日期”。由于后遇到的日期可能先被解决（比如：71, 69, 72，69先遇到72被解决），这符合后进先出的特性——栈。

3. 手绘模拟过程

以样例 [73, 74, 75, 71, 72] 为例，我们在草稿纸上画一个竖直的桶（栈），里面存下标：

1. i=0 (T=73)：栈为空，0号入栈。 Stack: {0}
2. i=1 (T=74)：发现 74 > 栈顶的 73。
   • 弹出 0，计算距离：$1 - 0 = 1$。$ans[0] = 1$。
   • 1号入栈。 Stack: {1}
3. i=2 (T=75)：发现 75 > 栈顶的 74。
   • 弹出 1，计算距离：$2 - 1 = 1$。$ans[1] = 1$。
   • 2号入栈。 Stack: {2}
4. i=3 (T=71)：发现 71 < 栈顶的 75。
   • 71 只能乖乖等待，3号入栈。 Stack: {2, 3}
5. i=4 (T=72)：发现 72 > 栈顶的 71。
   • 弹出 3，计算距离：$4 - 3 = 1$。$ans[3] = 1$。
   • 继续看栈顶：72 < 75，停止弹出。
   • 4号入栈。 Stack: {2, 4}

结论：栈内元素下标对应的温度，永远是单调递减的。

三、 算法流程图 (C++14 伪代码思路)

为了避免 Mermaid 语法解析特殊字符报错，我们使用文字描述逻辑节点。

graph TD
    A(开始遍历 i 从 0 到 n-1) --> B{栈不为空 且 当前温度 大于 栈顶下标对应温度}
    B -- 是 --> C(取出栈顶下标 topIndex)
    C --> D(计算距离 ans topIndex = i 减 topIndex)
    D --> B
    B -- 否 --> E(将当前下标 i 压入栈)
    E --> F{是否遍历完所有元素}
    F -- 否 --> A
    F -- 是 --> G(输出结果数组 ans)
    G --> H(结束)

四、 复杂度分析与优化

• 时间复杂度分析： 虽然代码里有 for 循环嵌套 while 循环，但请注意：每个元素最多只会入栈一次，出栈一次。 因此，总的操作次数是 $2n$，时间复杂度为 $O(n)$。这在 $10^5$ 的数据规模下可以轻松通过。

• 空间复杂度分析： 我们需要一个栈来存储下标，最坏情况下（温度严格递减）栈的大小为 $n$。 空间复杂度为 $O(n)$。

• 优化建议： 在 NOI 比赛中，为了追求极致效率，可以使用手写数组模拟 std::stack，并使用 scanf/printf 或快读进行输入输出。

五、 读题关键词总结 (题眼)

在处理这类线性序列问题时，若看到以下关键词，应第一时间联想到单调栈：

1. “最近/第一个”：寻找左侧或右侧第一个比当前值大/小的元素。
2. “等待天数/距离”：需要计算下标之差。
3. “矩形面积/接雨水”：这类需要确定左右边界的问题，通常也是单调栈的变体。
4. 数据范围 $10^5$ ~ $10^6$：提示你需要 $O(n)$ 或 $O(n \log n)$ 的算法，$O(n^2)$ 必死。

教练寄语：单调栈的精髓在于“及时排除不再可能贡献答案的冗余信息”。当你发现某个元素进入后，之前的某些元素就彻底失去了作为“未来答案”的意义时，就是单调栈大显身手的时候。加油！