【LeetCode】739.每日温度
目录
- 题目描述
- 输入输出示例及数据范围
- 思路：单调栈
- C++ 实现
题目描述
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
输入输出示例及数据范围
思路：单调栈
我们当然可以使用暴力求解的方式解决这道题，但是更优的做法是使用单调栈。具体来说，单调栈当中存储的是原数组的下标，并满足栈顶元素（下标）对应到原数组当中的值在栈中是最大的。
我们从头开始对 temperatures 数组进行遍历，并在遍历的过程中维护整个单调栈。对于第i个元素，我们首先不断地取栈顶的下标prev对应的元素temperatures[prev]与temperatures[i]比较大小，如果前者比后者小，那么说明prev 这个下标对应的这一天找到了与它最近且问题比它高的那一天，prev这一天的答案就是i - prev。不断地比较直至栈清空或是temperatures[prev]不比temperatures[i]小，此时将i入栈即可。
C++ 实现
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> ans(n, 0);
stack<int> st;
for(int i=0; i<n; i++) {
while(!st.empty() && temperatures[st.top()] < temperatures[i]) {
int prev = st.top();
ans[prev] = i - prev;
st.pop();
}
st.push(i);
}
return ans;
}
};