acwing 830 单调栈

题面

题解

1. 先考虑暴力做法 ,看数据范围1e5 ，O（n2）肯定过不了 ，那么我们考虑优化内层循环

for(int i=0;i<n;i++){   //循环每一个数
        for(int j=i-1;j>=0;j--){   //从这个数的左边开始往前找
            if(a[i]>a[j]){
                break;
            }
        }
    }
           

1. （重点）题中要求数左边离它最近且比它小的数，我们可以知道，如果ai >= a j ,那么对于aj 后边的数，肯定是不会用到 ai 的，因为有aj的存在，最优解一定是aj
2. 所以我们可以用一个单调栈（代码是用数组模拟栈）来维护，这个单调栈递增，从前往后遍历的时候，如果栈顶元素小于当前值x，那么这个值一定是离它最近小于它的点，如果是大于等于，那么就删除栈顶元素，继续比较直到小于或者栈为空，输出对应的答案，然后将这个x加入栈中（仍然是一个单调递增的栈），继续遍历

代码

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;

int n;
int stk[N], tt;

int main() {

    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        while (tt && stk[tt] >= x) tt--;
        if (tt) cout << stk[tt] << " ";
        else cout << -1 << " ";
        stk[++tt] = x;
    }
    return 0;
}