[C++知识库]830. 单调栈

由于每次要输出左边第一个比他小的数，如果不存在输出-1

先想想暴力怎么做，然后对暴力优化

for(int i=0;i<n;i++)
    for(int j=i-1;j>=0;j--)
        if(b[j]<b[i]) break...

对暴力的优化就是只保留有用的状态就可以了

每次要输出左边第一个比他小的数，我们在遍历到i时，把1~i-1所有数压入栈中，看看哪些是永远不会作为答案输出的，即永远不会被当成左边第一个比某数小的数的

每次要找到第一个比他小的数，都是不断弹栈，直到满足条件

?如图，当遍历到ai+1时，栈中的ai是比a1小的，往后的遍历中，一定是会先遇到ai，而a1比ai大，在后面的遍历中，是永远不会被输出的，所以a1应该去掉

利用这个性质，栈中的元素就会呈现单调递增的状态

当遍历到 ai 时，会不断弹栈 直到栈顶元素 <ai,这个时候再把ai 压进栈中，维护栈的单调性

#include <iostream>
using namespace std;

const int N=1e5+10;

int stk[N],tt;

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

?