1、題目描述

【題目鏈接】
給定一個(gè)整數(shù)數(shù)組 temperatures ，表示每天的溫度，返回一個(gè)數(shù)組 answer ，其中 answer[i] 是指對于第 i 天，下一個(gè)更高溫度出現(xiàn)在幾天后。如果氣溫在這之后都不會(huì)升高，請?jiān)谠撐恢糜?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

2、基本思路

?如果采用最簡單最暴力的方法，就是從當(dāng)前位置i的下一個(gè)位置i+1出發(fā)，找到第一個(gè)j，使得temperatures[j] > temperatures[i]，這種方法最壞情況得時(shí)間復(fù)雜度為O(n^2)。那么，有沒有更好得方法呢？答案是有的。
?采用單調(diào)棧的方法，維護(hù)一個(gè)從棧底到棧頂單調(diào)遞減的序列，舉個(gè)簡單的例子，例如溫度序列為【1，4，3，5，5，2，3，6】

• 初始化，?？?；
• 首先，?？?，1入棧（棧中元素[1]）;
• 第二個(gè)數(shù)4，與棧頂元素1比較，1<4，則出棧，且答案為res[1]=1，?？战Y(jié)束比較，4入棧（棧中元素[4]）；
• 第三個(gè)數(shù)3，與棧頂元素4比較，4>3，3入棧；（棧中元素[4,3]）；
• 第四個(gè)數(shù)5，與棧頂元素3比較，3<5，3出棧，答案為res[3]=1；（棧中元素[4]）；
• 棧非空，繼續(xù)與棧頂元素比較，4<5，4出戰(zhàn)，答案為res[2]=2；（棧中元素[]）；
• ?？眨?入棧（棧中元素[5]）；
• 第五個(gè)元素5，與棧頂元素5比較，5>=5，5入棧，（棧中元素[5，5]）；
• 第六個(gè)元素2，與棧頂元素5比較，5>2，2入棧，（棧中元素[5，5，2]）；
• 第七個(gè)元素3，與棧頂元素2比較，2<3，2出棧，且答案為res[6]=1，（棧中元素[5，5]）；
• 棧非空,繼續(xù)與棧頂元素5比較，5>3，3入棧，（棧中元素[5，5，3]）；
• 第八個(gè)元素6，與棧頂元素3比較，3<6，3出棧，且答案為res[7]=1，（棧中元素[5，5]）；
• 棧非空，與棧頂元素5比較，5<6，5出棧，且答案為res[4]=4，（棧中元素[5]）；
• 棧非空，與棧頂元素5比較，5<6，5出棧，且答案為res[5]=3，（棧中元素[]）；
• 棧為空且序列遍歷結(jié)束
  最終答案為[1,2,1,4,3,1,1,0]

?同樣，我們也可以維護(hù)一個(gè)從棧底到棧頂維護(hù)一個(gè)單調(diào)遞減的序列，遍歷的序列從右往左。

單調(diào)棧的基本思想——及時(shí)去掉無用的數(shù)據(jù)，保證棧中數(shù)據(jù)有序文章來源地址http://www.zghlxwxcb.cn/news/detail-821177.html

3、代碼實(shí)現(xiàn)

• 方法一

vector<int> solve1(vector<int> &temperatures)
{
    int n = temperatures.size();
    vector<int> res(n,0);
    stack<int> st;
    for(int i =0;i<n;++i)
    {
        int t = temperatures[i];
        while(!st.empty() && t> temperatures[st.top()])
        {
            res[st.top()] = i-st.top();
            st.pop() ;
        }
        st.push(i);

    }
    
    return res;

}

• 方法二

vector<int> solve(vector<int> &temperatures)
{
    int n = temperatures.size();
    vector<int> res(n,0);
    stack<int> st;
    for(int i =n-1;i>=0;i--)
    {
        int t = temperatures[i];
        while(!st.empty() && t>=temperatures[st.top()])
        {
            st.pop();
        }
        if(!st.empty())
        {
            res[i] = st.top()-i;
        }
        st.push(i);
    }
    return res;

}

到了這里，關(guān)于【LeetCode739】每日溫度的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！