题目
给定一个整数数组
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 <= temperatures.length <= 105
30 <= temperatures[i] <= 100
原题链接
Leetcode739.每日温度
思路1(暴力枚举)
- 暴力
遍历每一个元素,然后再从当前元素往后找比它大的,找到之后记录下他俩位置的差值,然后停止内层循环,如果没找到默认为0。
但是测试用例无法过完,O(N^2)的时间复杂度太高
文章来源:https://www.toymoban.com/news/detail-823937.html
代码1
class Solution
{
public:
vector<int> dailyTemperatures(vector<int>& a)
{
int n = a.size();
vector<int> res(n, 0);//用0初始化一个大小跟a一样得数组;
for(int i = 0; i < n; i++)//遍历第一个元素
{
for(int j = i + 1;j < n; j++)//从当前元素得下一个元素开始找比当前元素大的第一个
{
if(a[j] > a[i])
{
res[i] = j - i;
break;
}
}
}
return res;
}
};
思路2(单调栈)
遍历整个数组,如果栈不空,且当前数字大于栈顶元素,
取出栈顶元素
,由于当前数字大于栈顶元素的数字,而且一定是第一个大于栈顶元素的数,直接求出下标差就是二者的距离。
看向新的栈顶元素,直到当前数字小于等于栈顶元素停止,然后将数字入栈,
每个数字和第一个大于它的数的距离也可以算出来。O(N)的时间复杂度
文章来源地址https://www.toymoban.com/news/detail-823937.html
代码2
class Solution
{
public:
vector<int> dailyTemperatures(vector<int>& a)
{
vector<int> res(a.size(), 0);//开一个跟a大小一样的答案是数组
stack<int> st; //单调栈
for(int i = 0; i < a.size(); i++)遍历数组
{
while(!st.empty() && a[i] > a[st.top()])//如果栈不为空并且当前元素大于栈顶元素,那么计算栈顶元素的res并且出栈顶元素
{
res[st.top()] = i - st.top();
st.pop();
}
//如果当前元素小于或者等于栈顶元素,那么当前元素下标入栈
st.push(i);
}
return res;
}
};
到了这里,关于Leetcode739.每日温度的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!