題目
給定一個(gè)整數(shù)數(shù)組
temperatures，表示每天的溫度，返回一個(gè)數(shù)組answer，其中answer[i]是指對于第i天，下一個(gè)更高溫度出現(xiàn)在幾天后。如果氣溫在這之后都不會升高，請?jiān)谠撐恢糜?0來代替。
實(shí)例1
輸入: temperatures = [73,74,75,71,69,72,76,73]
輸出: [1,1,4,2,1,1,0,0]
實(shí)例2
輸入: temperatures = [30,40,50,60]
輸出: [1,1,1,0]
實(shí)例3
輸入: temperatures = [30,60,90]
輸出: [1,1,0]
提示
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100
原題鏈接
Leetcode739.每日溫度
思路1(暴力枚舉)
- 暴力
遍歷每一個(gè)元素，然后再從當(dāng)前元素往后找比它大的，找到之后記錄下他倆位置的差值，然后停止內(nèi)層循環(huán)，如果沒找到默認(rèn)為0。
但是測試用例無法過完，O(N^2)的時(shí)間復(fù)雜度太高文章來源：http://www.zghlxwxcb.cn/news/detail-823937.html
代碼1
class Solution
{
public:
vector<int> dailyTemperatures(vector<int>& a)
{
int n = a.size();
vector<int> res(n, 0);//用0初始化一個(gè)大小跟a一樣得數(shù)組；
for(int i = 0; i < n; i++)//遍歷第一個(gè)元素
{
for(int j = i + 1;j < n; j++)//從當(dāng)前元素得下一個(gè)元素開始找比當(dāng)前元素大的第一個(gè)
{
if(a[j] > a[i])
{
res[i] = j - i;
break;
}
}
}
return res;
}
};
思路2(單調(diào)棧)
遍歷整個(gè)數(shù)組，如果棧不空，且當(dāng)前數(shù)字大于棧頂元素，
取出棧頂元素，由于當(dāng)前數(shù)字大于棧頂元素的數(shù)字，而且一定是第一個(gè)大于棧頂元素的數(shù)，直接求出下標(biāo)差就是二者的距離。
看向新的棧頂元素，直到當(dāng)前數(shù)字小于等于棧頂元素停止，然后將數(shù)字入棧，每個(gè)數(shù)字和第一個(gè)大于它的數(shù)的距離也可以算出來。O(N)的時(shí)間復(fù)雜度文章來源地址http://www.zghlxwxcb.cn/news/detail-823937.html
代碼2
class Solution
{
public:
vector<int> dailyTemperatures(vector<int>& a)
{
vector<int> res(a.size(), 0);//開一個(gè)跟a大小一樣的答案是數(shù)組
stack<int> st; //單調(diào)棧
for(int i = 0; i < a.size(); i++)遍歷數(shù)組
{
while(!st.empty() && a[i] > a[st.top()])//如果棧不為空并且當(dāng)前元素大于棧頂元素，那么計(jì)算棧頂元素的res并且出棧頂元素
{
res[st.top()] = i - st.top();
st.pop();
}
//如果當(dāng)前元素小于或者等于棧頂元素，那么當(dāng)前元素下標(biāo)入棧
st.push(i);
}
return res;
}
};
到了這里，關(guān)于Leetcode739.每日溫度的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![【LeetCode】數(shù)據(jù)結(jié)構(gòu)題解（6）[回文鏈表]](https://imgs.yssmx.com/Uploads/2024/02/434983-1.png)
![【LeetCode】數(shù)據(jù)結(jié)構(gòu)題解（5）[分割鏈表]](https://imgs.yssmx.com/Uploads/2024/02/444977-1.png)
