739. 每日温度

题目描述

请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

解题思路

暴力法
对每个元素，从前往后遍历数组，找到大于该元素的最近一个元素，时间复杂度为O(n^2)。
借助栈。
可以维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。
将元素下标入栈，当有新元素i下标入栈时，和栈顶prev比较大小，如果更大，则可以更新栈顶prev的值=i-prev，然后pop栈顶，如此栈为空或者比栈顶小。然后将i入栈。举例来说：
对于温度列表 [73,74,75,71,69,72,76,73][73,74,75,71,69,72,76,73]，单调栈 \textit{stack}stack 的初始状态为空，答案 \textit{ans}ans 的初始状态是 [0,0,0,0,0,0,0,0][0,0,0,0,0,0,0,0]，按照以下步骤更新单调栈和答案，其中单调栈内的元素都是下标，括号内的数字表示下标在温度列表中对应的温度。

当 i=0时，单调栈为空，因此将 0 进栈。
$\textit{stack}=[0(73)]$
$\textit{ans}=[0,0,0,0,0,0,0,0]$

当 i=1时，由于 74 大于 73，因此移除栈顶元素 0，赋值 ans[0]:=1-0，将 1 进栈。
$\textit{stack}=[1(74)]$
$\textit{ans}=[1,0,0,0,0,0,0,0]$

当 i=2 时，由于 75 大于 74，因此移除栈顶元素 1，赋值 ans[1]:=2-1，将 2 进栈。
$\textit{stack}=[2(75)]$
$\textit{ans}=[1,1,0,0,0,0,0,0]$

当 i=3时，由于 71 小于 75，因此将 3 进栈。
$\textit{stack}=[2(75),3(71)]$
$\textit{ans}=[1,1,0,0,0,0,0,0]$

当 i=4时，由于 69 小于 71，因此将4 进栈。
$\textit{stack}=[2(75),3(71),4(69)]$
$\textit{ans}=[1,1,0,0,0,0,0,0]$

当 i=5时，由于 72大于 69 和 71，因此依次移除栈顶元素 44和 3，赋值 ans[4]:=5-4和 ans[3]:=5-3，将 5 进栈。
$\textit{stack}=[2(75),5(72)]$
$\textit{ans}=[1,1,0,2,1,0,0,0]$

当 i=6 时，由于 76 大于 72 和 75，因此依次移除栈顶元素 5 和 2，赋值 ans[5]:=6-5 和 ans[2]:=6-2，将 6 进栈。
$\textit{stack}=[6(76)]stack=[6(76)]$
$\textit{ans}=[1,1,4,2,1,1,0,0]$

当i=7 时，由于 73 小于 76，因此将 7 进栈。
$\textit{stack}=[6(76),7(73)]stack=[6(76),7(73)]$
$\textit{ans}=[1,1,4,2,1,1,0,0]ans=[1,1,4,2,1,1,0,0]$

    vector<int> dailyTemperatures(vector<int>& T) {
        vector<int> ret(T.size(), 0);
        stack<int> s;
        s.push(0);
        for(int i=1; i<T.size(); i++){
            if(T[i]>T[s.top()]){
                while(!s.empty() && T[i]>T[s.top()]){
                    int prev = s.top();
                    ret[prev] = i-prev;
                    s.pop();
                }
            }
            s.push(i);
        }
        return ret;
    }