【数据结构】单调栈

首先，单调栈是什么？

定义：

单调栈：单调递增或单调递减的栈

这句话说了就和说了句话一样，但是确实，单调栈正如它字面表达出来的含义一样，是一个内部元素保持单调的栈。

直接看一个例子：

题面：

代码：

#include<iostream>
#include<cstdio>
#include<string>
#include<stack>
using namespace std;
stack <int> pig,mpig;
string cmd;
int main(void){
    int n;
    while(cin>>cmd){
        if(cmd=="push"){
            scanf("%d",&n);
            if(!pig.empty()){
                pig.push(n);
                if(n<=mpig.top()) mpig.push(n);
            }else{
                pig.push(n);
                mpig.push(n);
            }
        }else if(cmd=="pop"){
            if(!pig.empty())
                if(pig.top()!=mpig.top()) pig.pop();
                else{
                    pig.pop();
                    mpig.pop();
                }
            else continue;
        }else{
            if(!mpig.empty()) printf("%d\n",mpig.top());
            else continue;
        }
    }
    return 0;
}

上述代码中的mpig栈就是一个单调栈。

代码正确性很简单：

• push时：倘若新叠上的猪比现在猪堆中最轻的猪要重，那么这头猪永远不可能作为min的答案，则没有必要加入mpig栈中；倘若新叠上的猪重量小于等于猪堆中最轻的猪，那么这头猪可能作为答案，需要压入mpig栈中。

• pop时：倘若pig栈顶的猪重于mpig栈顶的猪，那么这只猪不可能被压入过mpig栈，直接pig.pop( )即可；倘若pig栈顶的猪与mpig栈顶的猪重量相等，那么这只猪曾经一定也被压入过mpig栈中，pig.pop( )的同时需要mpig.pop( )。

• min时：mpig栈顶元素即为此时猪堆中最轻猪。