[编程笔记]-Monotonic_Stack单调栈

简介

具有单调性的栈（站内元素单调递增或单调递减）

常见题型

问数组中每一个元素左侧/右侧离它最近的比它大/小的元素是什么。

代码

class Monotonic_Stack{//这里是单调递减，要改的话改fix()就行了。
    public:
        int a[N];
        int size;
        bool empty(){
            return size==0;
        }
        int top(){
            return a[size];
        }
        void pop(){
            size--;
        }
        void fix(int x){//维护单调性
            while(!empty()&&top()>=x)pop();
        }
        void push(int x){//单调插入
            fix(x);
            a[++size]=x;
        }
}ms;

例题

就是上面说的经典题型。

AcWing830-单调栈

讲解

还是讲解一下吧。

维护栈单调性可做的证明：

若a[i]≥aj，那么在j之后所有结果可以是i的，j都会是更优解。所以i绝对不可能作为答案出现，可以排除。

这样，就只需要维护一个单调递增的栈就行了。

代码

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;

class Monotonic_Stack{
    public:
        int a[N];
        int size;
        bool empty(){
            return size==0;
        }
        int top(){
            return a[size];
        }
        void pop(){
            size--;
        }
        void fix(int x){
            while(!empty()&&top()>=x)pop();
        }
        void push(int x){
            fix(x);
            a[++size]=x;
        }
}ms;

int n;
int a[N];

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        ms.fix(a[i]);
        if(!ms.empty()) cout<<ms.top();
        else cout<<-1;
        cout<<" ";
        ms.push(a[i]);
    }
    return 0;
}

完结撒花o(￣︶￣)o