739. Daily Temperatures（medium）

题目描述

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.
For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].
Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

解题思路

主要是构建一个递减栈来存储这个后面比当前i的坐标大的温度的下下标，然后用一个vector来存储最后的结果，最后的结果result=第一个比自己大的temperature的下标-当前的的下标，即是这个元素对应的结果。最后一个元素不进行处理，因为已经到最后了，所以说肯定是0.
对栈内元素的处理，首先如果栈内元素为0，则这个元素返回的结果就是0；如果遍历到的元素值大于栈顶的元素，则栈顶的元素出栈，直到当前栈顶的元素是比当前的元素大的时候结束，这时候栈顶元素（是对应的下标）-当前元素的下标，即为最终结果

下面是对应的代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        vector<int>ans(T.size(),0);//initial the empty vector to conserve the result
        stack<int>res;//build a decrease stack
        for(int i=T.size()-1;i>=0;--i)//Traversing the vector,and the last one h is null, so skip it
        {
            while(!res.empty()&&T[i]>=T[res.top()])
                res.pop();
            if(res.empty())
                ans[i]=0;
            else
                ans[i]=res.top()-i;
            res.push(i);
        }
        return ans;
    }

};

int main(){

    //test example
    int a[]={73, 74, 75, 71, 69, 72, 76, 73};
    vector<int> vec1;
    for(int i=0;i<8;i++)
    vec1.push_back(a[i]);
    Solution s;
    vector<int> ans=s.dailyTemperatures(vec1);
    for(int i=0;i<ans.size();i++)
        cout<<ans[i]<<" ";
    return 0;

}