O(n) solution C++ using stack


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

#2

If we consider the worst case where the array given is in decreasing order
INPUT : [5,4,3,2,1]
Here the time complexity will be (according to this code) O(n^2).
Since, for loop will run n times.
The stack will collect n-1 elements till i=(n-1), so the while loop will execute (n-1) times for last element.
Thus, time comlexity: n*(n-1) i.e. O(n^2).
Please correct me if i am skipping any point.