Easy C++ solution using stacks with O(n) time complexity


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