Leetcode 739.每日温度 单调栈

问题描述

每日温度：原题链接

思路

非常直接的单调栈问题
是这一道题的变种
leetcode 503.下一个更大元素II

代码

class Solution {
    
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
    
        pair<int,int> tem[temperatures.size()];
        for(int i=0;i<temperatures.size();i++)
            tem[i]={
    i,temperatures[i]};

        stack<pair<int,int>> s; //栈内存储的元素得既有下标又有温度，因为这里求的是相隔的天数
        vector<int> res;

        for(int i=temperatures.size()-1;i>=0;i--)
        {
    
            while(!s.empty()&&s.top().second<=tem[i].second) //比较的是温度
                s.pop();
            if(s.empty())
                res.push_back(0);
            else 
                res.push_back(s.top().first-tem[i].first);  //实际输出的是天数
            s.push(tem[i]);
        }
        reverse(res.begin(),res.end());
        return res;
    }
};