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

LeetCode-栈-每日温度

ops 2025/7/22 14:16:27

LeetCode-栈-每日温度

✏️ 关于专栏：专栏用于记录 prepare for the coding test。

文章目录

LeetCode-栈-每日温度
- 📝每日温度
- - 🎯题目描述
  - 🔍 输入输出示例
  - 🧩题目提示
  - 🧪AC
- 🌟 总结

📝每日温度

🎯题目描述

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

🔗题目链接：每日温度

🔍 输入输出示例

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]xxxxxxxxxx 输入: temperatures = [30,60,90]输出: [1,1,0]输入：s = "(]"输出：false

🧩题目提示

1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

🧪AC

本题的关键在于找到当前温度后面第一个更高温度出现的天数。如果没有更高温度，则返回 0。

考虑一个**单调栈（Monotonic Stack）**的应用场景：

我们使用一个栈来存放“尚未找到更高温度的索引”。
当遇到比栈顶元素所代表温度更高的温度时，就意味着我们可以为栈顶元素“结账”，也就是算出它距离下一个更高温度的间隔。
重复这个过程，直到栈为空或栈顶对应温度高于当前温度。

1、初始化结果数组 ans，长度与 temperatures 一致，初始值为 0。

2、创建一个栈 st，用于存储下标。

3、遍历数组中的温度值：

如果当前温度 t 大于栈顶下标所对应的温度，则不断弹出栈顶，计算 ans[j] = i - j。
最后将当前下标压入栈中。

4、返回 ans。

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int>ans(n);stack<int>st;for(int i = 0;i < n;i++){int t = temperatures[i];while(!st.empty()&&t > temperatures[st.top()]){int j = st.top();st.pop();ans[j] = i - j;}st.push(i);}return ans;}
};

stack<int> st: 栈中存放的是下标而不是温度，方便计算天数差。

while 循环检查当前温度是否能“解锁”栈中等待的温度。