单调栈

先想一下暴力做法，然后优化
适用题型：找到a[i] 前面离他 左边最近 且 比他小 的数。

如果 存在a[x]>=a[y] 且 x[HTML_REMOVED]=x 那么让a[tt]出栈就好了 tt–
直到找到 a[tt]<x 再把x插到栈顶。

这个题sancf可以比cin 快10倍左右。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5+10;

int n;
int stk[N],tt;

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

        stk[++tt]=x;
    }


    return 0;
}