单调栈原理

我们知道,既然每次找到左边第一个比自己小的数, 那么每次我们栈中只需要保存小于这个数的所有int类型就可以啦,
那么每一步我们都会把大于这个数的栈内元素出栈,所以我们最后得到的是一个单调的栈;

C++代码

#include<iostream>
using namespace std;
int top = 0;
const int N = 1e5 + 10;
int a[N], b[N];
int main()
{
    int n; cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];


    for(int i = 0; i < n; i++)
    {
        while(top && b[top] >= a[i]) top--;//如果栈顶元不小于这个数, 则出栈
        if(top) cout << b[top] << " ";
        else cout << "-1" << " ";
        b[++top] = a[i];//记录入栈顶
    }

    return 0;
}