739. 每日温度
3 min
题目
解法：单调栈
思路
使用单调递减栈存储尚未找到更高温度的日期下标，正向遍历数组时，一旦遇到比栈顶温度高的日期，就立即为栈顶日期计算结果。
正确性基于栈的单调性。栈中下标对应的温度严格递减，因此当 temperatures[i] > temperatures[st.top()] 时，i 必然是 st.top() 之后第一个更高温度的天。如果存在更早的更高温度，该栈顶元素早已在之前被弹出，因此不会遗漏解。
- Step 1: 初始化结果数组 res(n, 0) 和空栈 st
- Step 2: 遍历每一天 i，当栈非空且 temperatures[i] > temperatures[st.top()] 时，执行 res[st.top()] = i - st.top() 并弹出栈顶
- Step 3: 将当前下标 i 入栈
- Step 4: 遍历结束后返回 res
复杂度
- 时间复杂度:
- 空间复杂度:
代码
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> res(n, 0);
stack<int> st; // 存储数组下标
for(int i = 0;i < n;i++){
while(!st.empty() and temperatures[i] > temperatures[st.top()]){
res[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
return res;
}
};