C++ O(n) in space and O(n*logn) in time


#1
vector<int> Solution::nextGreater(vector<int> &A) {
    int n = A.size();
    if(n == 0)
        return vector<int>();
    vector<int> ans(n);
    set<int> greater;
    for(int i=n-1; i>=0; --i){
        int v = A[i];
        auto it = greater.upper_bound(v);
        if(it == greater.end()){
            greater.clear();
            ans[i] = -1;
        }
        else
            ans[i] = *it;
        greater.insert(v);
    }
    return ans;
}