当前位置：首页 > news >正文

[LeetCode]每日温度

news 2025/7/26 8:39:20

题目链接

每日温度

题目描述

思路解析：单调栈

单调栈介绍：

单调栈是一种特殊的栈数据结构，其核心特性是栈内元素始终保持单调递增或单调递减的顺序。这种特性使其在解决「寻找下一个更大 / 更小元素」「区间最值」等问题时具有极高效率，时间复杂度通常为 O (n)。

一、单调栈的核心特性

1。单调性：栈内元素按照某种规则（递增或递减）严格排序

单调递增栈：栈顶元素 ≥ 栈底元素（从栈顶到栈底递增）
单调递减栈：栈顶元素 ≤ 栈底元素（从栈顶到栈底递减）

2.操作规则：

新元素入栈前，先弹出所有破坏单调性的栈顶元素
确保入栈后仍保持原有单调性
弹出的元素通常能找到「第一个符合条件的元素」

二、典型应用场景

寻找数组中每个元素的「下一个更大元素」
寻找数组中每个元素的「下一个更小元素」
计算柱状图中能接多少雨水
计算最大矩形面积
解决「每日温度」问题（如前文代码）

三、工作原理演示

下面分别用单调递增栈和单调递减栈处理数组[1,4,3,5,5,2,3,6]，并展示处理过程。

1. 单调递增栈（栈内元素从栈底到栈顶递增）

核心规则：新元素入栈时，弹出所有小于当前元素的栈顶元素（确保栈的递增性），再将当前元素入栈。

处理过程（数组索引 0 到 7，元素依次为 1,4,3,5,5,2,3,6）：

步骤	当前元素	栈操作（弹出小于当前元素的栈顶）	栈状态（栈底→栈顶）
0	1	栈空，直接入栈	[1]
1	4	4 > 1（栈顶），直接入栈	[1,4]
2	3	3 <4（栈顶），弹出 4；3> 1，入栈	[1,3]
3	5	5 > 3（栈顶），直接入栈	[1,3,5]
4	5	5 = 5（栈顶），直接入栈（保持递增）	[1,3,5,5]
5	2	2 <5（栈顶）→弹出 5；2 < 5→弹出 5；2 < 3→弹出 3；2> 1，入栈	[1,2]
6	3	3 > 2（栈顶），直接入栈	[1,2,3]
7	6	6 > 3（栈顶），直接入栈	[1,2,3,6]

最终栈状态：[1,2,3,6]（严格递增）

2. 单调递减栈（栈内元素从栈底到栈顶递减）

核心规则：新元素入栈时，弹出所有大于当前元素的栈顶元素（确保栈的递减性），再将当前元素入栈。

处理过程：

步骤	当前元素	栈操作（弹出大于当前元素的栈顶）	栈状态（栈底→栈顶）
0	1	栈空，直接入栈	[1]
1	4	4 > 1（栈顶），弹出 1；栈空，入栈 4	[4]
2	3	3 < 4（栈顶），直接入栈	[4,3]
3	5	5 > 3（栈顶）→弹出 3；5 > 4→弹出 4；栈空，入栈 5	[5]
4	5	5 = 5（栈顶），直接入栈（保持递减）	[5,5]
5	2	2 < 5（栈顶），直接入栈	[5,5,2]
6	3	3 > 2（栈顶）→弹出 2；3 < 5，入栈	[5,5,3]
7	6	6 > 3（栈顶）→弹出 3；6 > 5→弹出 5；6 > 5→弹出 5；栈空，入栈 6	[6]

最终栈状态：[6]（严格递减）

总结

单调递增栈适合寻找「元素右侧第一个更小元素」等场景，栈内始终保持 "后入元素更大" 的特性。
单调递减栈适合寻找「元素右侧第一个更大元素」等场景，栈内始终保持 "后入元素更小" 的特性。
相等元素的处理可根据需求调整（本文保留相等元素以维持单调性）。

题目解析

一：从右往左

核心思路详解

1. 问题转化

对于数组中的每个元素 temperatures[i]，我们需要找到最小的 j > i 使得 temperatures[j] > temperatures[i]，结果为 j - i；如果不存在这样的 j，结果为 0。

2. 单调栈的设计

栈的作用：存储温度数组的索引，且这些索引对应的温度值从栈顶到栈底是递增的（单调递增栈）。
为什么用索引：既需要比较温度值，又需要计算位置差（天数），存储索引可以同时获取这两个信息。

3. 遍历方向：从后往前

从数组末尾开始遍历，确保处理当前元素 i 时，其右侧的所有元素都已被处理，栈中已保存了右侧可能的 “更高温度” 候选。

4. 关键步骤（以当前索引 `i` 为例）

步骤 1：清除无效候选
当栈不为空，且栈顶索引对应的温度 ≤ 当前温度 temperatures[i] 时，说明栈顶元素不可能是 i 的 “下一个更高温度”（因为当前温度更高），将其弹出。

while (!st.empty() && temperatures[i] >= temperatures[st.top()]) {st.pop();
}

步骤 2：计算结果
经过步骤 1 后，若栈仍不为空，栈顶索引就是 i 右侧第一个比它温度高的位置，两者的差就是结果：

if (!st.empty()) {ans[i] = st.top() - i;  // 天数差 = 更高温度位置 - 当前位置
} else {ans[i] = 0;  // 没有更高温度
}

步骤 3：入栈当前索引
将当前索引 i 压入栈中，作为其左侧元素的 “更高温度” 候选：

st.push(i);

5. 示例理解

以 temperatures = [73, 74, 75, 71, 69, 72, 76, 73] 为例：

遍历到 i=6（温度 76）：栈为空，ans[6]=0，栈中压入 6。
遍历到 i=5（温度 72）：栈顶是 6（76>72），ans[5]=6-5=1，栈中压入 5。
遍历到 i=4（温度 69）：栈顶是 5（72>69），ans[4]=5-4=1，栈中压入 4。
... 以此类推，最终得到结果 [1,1,4,2,1,1,0,0]。

完整代码：

复杂度分析
时间复杂度：O(n)，其中 n 为 temperatures 的长度。虽然我们写了个二重循环，但站在每个元素的视角看，这个元素在二重循环中最多入栈出栈各一次，因此循环次数之和是 O(n)，所以时间复杂度是 O(n)。
空间复杂度：O(min(n,U))，其中 U=max(temperatures)−min(temperatures)+1。返回值不计入，仅考虑栈的最大空间消耗。

二：从左到右

思路类似：

问题目标：对于数组中的每个元素 temperatures[i]，找到下一个比它大的元素的索引 j，计算 j - i 作为结果；若不存在则为 0。
核心思路：使用单调栈（单调递减栈）存储温度的索引，栈内元素对应的温度始终保持递减顺序。通过遍历数组，对每个温度 temperatures[i]：
- 若当前温度 > 栈顶索引对应的温度，说明栈顶元素的 “下一个更高温度” 就是当前温度，计算间隔天数并弹出栈顶。
- 重复上述过程，直到栈空或当前温度 ≤ 栈顶温度，再将当前索引入栈。
时间复杂度：O (n)，每个元素最多入栈和出栈各一次。
空间复杂度：O (n)，栈的最大存储量为 n（极端情况：温度单调递减时，所有元素入栈）。