LeetCode 第 739 题：每日温度（Daily Temperatures） 题目描述 给定一个整数数组 temperatures ，表示每天的温度。你需要返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，至少要等多少天才能出现一个比当天温度更高的温度。如果未来没有这样的天数，则 answer[i] 为 0。 示例 输入： temperatures = [73,74,75,71,69,72,76,73] 输出： [1,1,4,2,1,1,0,0] 解题思路 这个问题可以转化为：对于数组中的每个元素，找到它右边第一个比它大的元素，并计算两者下标的距离。 直接使用双重循环（暴力法）会超时，因此我们采用 单调栈 来高效解决。 逐步讲解 步骤 1：理解暴力法的不足 对于每个温度 temperatures[i] ，向后遍历找到第一个 temperatures[j] > temperatures[i] ，则 answer[i] = j - i 。 时间复杂度 O(n²)，在数据量大时效率低。 步骤 2：引入单调栈 单调栈是一种栈结构，其中的元素保持单调递增或递减的顺序。 在这里，我们维护一个 单调递减栈 ，栈中存放的是温度的 下标 （因为需要计算天数差）。 遍历温度数组，对于每个温度： 如果当前温度 ≤ 栈顶那天的温度，将当前下标入栈（因为栈仍是递减的）。 如果当前温度 > 栈顶那天的温度，说明找到了栈顶那天的“下一个更高温度”，计算天数差，并弹出栈顶。重复此过程直到当前温度 ≤ 栈顶温度或栈为空。 步骤 3：详细推演示例 以 temperatures = [73,74,75,71,69,72,76,73] 为例： 初始化 answer = [0,0,0,0,0,0,0,0] ，栈 stack = [] 。 第 0 天（73）：栈空，入栈 [0] 。 第 1 天（74）：74 > 73（栈顶），弹出 0， answer[0] = 1 - 0 = 1 。栈空，入栈 [1] 。 第 2 天（75）：75 > 74，弹出 1， answer[1] = 2 - 1 = 1 。栈空，入栈 [2] 。 第 3 天（71）：71 ≤ 75，入栈 [2,3] 。 第 4 天（69）：69 ≤ 71，入栈 [2,3,4] 。 第 5 天（72）：72 > 69，弹出 4， answer[4] = 5 - 4 = 1 ；72 > 71，弹出 3， answer[3] = 5 - 3 = 2 ；72 ≤ 75，入栈 [2,5] 。 第 6 天（76）：76 > 72，弹出 5， answer[5] = 6 - 5 = 1 ；76 > 75，弹出 2， answer[2] = 6 - 2 = 4 。栈空，入栈 [6] 。 第 7 天（73）：73 ≤ 76，入栈 [6,7] 。 遍历结束，栈中剩余的下标对应 answer 为 0（因为没有更高温度）。 最终 answer = [1,1,4,2,1,1,0,0] 。 步骤 4：代码实现要点 使用栈存储下标。 遍历时，若当前温度大于栈顶下标对应的温度，则不断弹出栈顶并计算天数差。 最后栈中剩余的下标对应的 answer 值保持为 0（初始化值）。 复杂度分析 时间复杂度：O(n)，每个元素最多入栈、出栈一次。 空间复杂度：O(n)，最坏情况下栈的大小为 n。 通过单调栈，我们高效地解决了“找下一个更大元素”的问题。