C++ O(n) in both space and time


#1
vector<int> Solution::nextGreater(vector<int> &A) {
    int n = A.size();
    if(n == 0)
        return vector<int>();
    vector<int> ans(n);
    stack<int> s;
    for(int i=n-1; i>=0; --i){
        int v = A[i];
        while(!s.empty() and s.top() <= v)
            s.pop();
        if(s.empty())
            ans[i] = -1;
        else
            ans[i] = s.top();
        s.push(v);
    }
    return ans;
}