Two solutions with c++


  • 1
    E

    Solution 1:binary search

    class Solution {
    public:
        vector<int> dailyTemperatures(vector<int>& temperatures) {
            multimap<int,int>hash;
            vector<int>res(temperatures.size(),0);
            for(int i=0;i<temperatures.size();i++){
                auto it=hash.lower_bound(temperatures[i]);
                for(auto it2=it;it2!=hash.begin();){
                    it2--;res[it2->second]=i-it2->second;
                }
                hash.erase(hash.begin(),it);
                hash.emplace_hint(hash.begin(),temperatures[i],i);
            }
            return res;
        }
    };
    //Runtime:252ms
    

    Solution 2:stack

    class Solution {
    public:
        vector<int> dailyTemperatures(vector<int>& temperatures) {
            stack<pair<int,int> >s;
            vector<int>res(temperatures.size(),0);
            for(int i=0;i<temperatures.size();i++){
                while(!s.empty()&&temperatures[i]>s.top().first){
                    res[s.top().second]=i-s.top().second;
                    s.pop();
                }
                s.push(pair<int,int>(temperatures[i],i));
            }
            return res;
        }
    };
    //Runtime:232ms
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.