Easy stack approach O(n) solution


#1
vector<int> Solution::nextGreater(vector<int> &A) {


vector<int>ans;
if(A.size()==1)
{
    ans.push_back(-1);
    return ans;
}

stack<int>s;

ans.push_back(-1);

s.push(A[A.size()-1]);

for(int i=A.size()-2;i>=0;i--)
{
    
    if(A[i]<s.top())
    {
        ans.push_back(s.top());
        s.push(A[i]);
    }
    else
    {
        s.pop();
        
        while(s.size()!=0)
        {
            if(A[i]<s.top())
            {
                ans.push_back(s.top());
                s.push(A[i]);
                break;
            }
            
            else
            s.pop();
        }
        
        if(s.size()==0)
        {
            ans.push_back(-1);
            s.push(A[i]);
        }
    }
    
}

reverse(ans.begin(),ans.end());

return ans;

}


#2

The Worst-Case Time Complexity will be O(n*n). You did not account for the time complexity of while loop.