[LeetCode]每日温度

题目链接

每日温度

题目描述

 

思路解析 ：单调栈

单调栈介绍：

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

一、单调栈的核心特性

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

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

2.操作规则：

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

二、典型应用场景

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

三、工作原理演示 

下面分别用单调递增栈和单调递减栈处理数组[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 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 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。返回值不计入，仅考虑栈的最大空间消耗。

 二：从左到右

思路类似：

1. 问题目标：对于数组中的每个元素 temperatures[i]，找到下一个比它大的元素的索引 j，计算 j - i 作为结果；若不存在则为 0。

2. 核心思路：使用单调栈（单调递减栈）存储温度的索引，栈内元素对应的温度始终保持递减顺序。通过遍历数组，对每个温度 temperatures[i]：

   • 若当前温度 > 栈顶索引对应的温度，说明栈顶元素的 “下一个更高温度” 就是当前温度，计算间隔天数并弹出栈顶。
   • 重复上述过程，直到栈空或当前温度 ≤ 栈顶温度，再将当前索引入栈。

3. 时间复杂度：O (n)，每个元素最多入栈和出栈各一次。

4. 空间复杂度：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]。