Short C++ O(n) space O(nlogn) time


  • 0
    B
        vector<int> nextGreaterElements(vector<int>& nums) {
            vector<int> v, res;
            for(int num:nums) {
                if(v.empty() || num>v.back()) v.push_back(num);
            }
            for(int i=(int)nums.size()-1;i>=0;i--) {
                auto it = upper_bound(v.begin(), v.end(), nums[i]);
                res.push_back((it==v.end())?-1:*it);
                while(!v.empty() && nums[i]>=v[0]) v.erase(v.begin());
                v.insert(v.begin(), nums[i]);
            }
            reverse(res.begin(), res.end());
            return res;
        }
    

  • 0
    V

    Are you sure it's O(nlogn) ?
    v.erase(v.begin()) is O(n), so I think the time complexity is O(n^2).


  • 0
    B

    You are right! Deque should be used instead


Log in to reply
 

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