题目要求

给定一个长度为 N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1

最初想法

最初我想用双指针算法解决，以下是代码

    int l=0;
    for(int i=0;i<m;i++){
        int j=i-1;
        bool flag=false;
        while(j>=l&&flag==false){
            if(a[j]>=a[i]) j--;
            else {
                flag=true;
                cout<<a[j]<<" ";
            }
        }
        //当所有元素都大于a[i]时，将后面j的左端点l移至i
        if(!flag) {
            cout<<-1<<" ";
            l=i;
        }   
    }
    //时间复杂度分析：正常情况下，时间复杂度为O(n);
    从第二个数开始，数组降序排列时，时间复杂度为O（n²）
}

算法缺陷：

虽然l指针的移动动态维护了j的左边界，但是只能在左边整体为降序排列时简化运算，不能将无效的降序部分抛出

最坏情况：

从第二个数开始，数组降序排列时，时间复杂度为O（n²）

对单调栈的理解：

实质上就是解决了双指针算法无法抛出的问题：当目标数左侧存在降序部分时，将其全部抛出，这样就避免了后续重复遍历这一部分的问题；由于抛出了所有降序部分，也就相当于维护了栈的单调排列