[LeetCode]每日温度
题目链接
每日温度
题目描述
思路解析 ：单调栈
单调栈介绍：
单调栈是一种特殊的栈数据结构，其核心特性是栈内元素始终保持单调递增或单调递减的顺序。这种特性使其在解决「寻找下一个更大 / 更小元素」「区间最值」等问题时具有极高效率，时间复杂度通常为 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（极端情况：温度单调递减时，所有元素入栈）。
完整代码：
以 temperatures = [73, 74, 75, 71, 69, 72, 76, 73] 为例：
- 遍历到 74（索引 1）时，栈顶是 73（索引 0），74>73，故
ans[0] = 1-0=1，弹出 0，将 1 入栈。 - 遍历到 75（索引 2）时，栈顶是 74（索引 1），75>74，
ans[1]=2-1=1，弹出 1，将 2 入栈。 - 后续过程类似，最终结果为
[1,1,4,2,1,1,0,0]。