力扣739. 每日温度
给定一个整数数组 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]
暴力法(1个测试用例超时)
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n =temperatures.size();
vector<int> ans(n,0);
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(temperatures[j]>temperatures[i]){
ans[i]=j-i;
break;
}
}
}
return ans;
}
};
单调栈
class Solution {
public:
//栈底->栈顶单调递减栈,时间复杂度O(N),空间复杂度O(N)
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n =temperatures.size();
vector<int> ans(n,0);//初始化为0,最后无法升温时ans内元素及为0
stack<int> st;
for(int i=0;i<n;i++){//栈不空且当天温度大于栈顶那天温度则一直出栈,说明到了前面几天入栈日子的升温日
while(!st.empty()&&temperatures[i]>temperatures[st.top()]){
int index=st.top();st.pop();
ans[index]=i-index;
}
st.push(i);//入栈的是下标而非温度
}
return ans;
}
};
原文地址:https://blog.csdn.net/akdjfhx/article/details/140734068
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!