Solution of NEXTGREATER in O(n) using stack


#1

vector Solution::nextGreater(vector &A) {
stack s;
vector v;
int n= A.size();
for(int i=n-1;i>=0;i–)
{
if(s.size()==0)
v.push_back(-1);
else if(s.size()>0&&s.top()>A[i])
v.push_back(s.top());
else if(s.size()>0&&s.top()<=A[i])
{
while(s.size()>0&&s.top()<=A[i])
s.pop();
if(s.size()==0)
v.push_back(-1);
else
v.push_back(s.top());

    }
    s.push(A[i]);
    
}
reverse(v.begin(),v.end());
return v;

}