一、什么是栈

  • 栈是一种数据结构，它符合 “先进后出” 的规则

二、栈的应用——括号匹配问题

题意
第一行输入一个数N（0<N<=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有"[","]","(",")"四种字符
如((()[])) 这就是合法的，检测输入是否合法。
题目思路：
仔细想会发现这个地方的线性顺序是和入栈顺序是一样的，我们只需要考虑又括号即可，如果当前为左括号，就给他放入栈中(成为栈顶)。若果为右括号需要看一下当前栈顶元素是否匹配，如果不匹配就直接break即可，如果匹配那就消除，栈顶元素更新。
题目代码

char str[maxn];
char st[maxn];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int bg=0;bool flag=true;
        scanf("%s",str+1);
        for(int i=1;str[i];i++)
        {
            if(str[i]=='[')
                st[++bg]=str[i];
            if(str[i]=='(')
                st[++bg]=str[i];
            if(str[i]==']')
            {
                if(st[bg]=='[')
                    bg--;
                else
                {
                    flag=false;
                    break;
                }
            }
            if(str[i]==')')
            {
                if(st[bg]=='(')
                    bg--;
                else
                {
                    flag=false;
                    break;
                }
            }
        }
        if(!flag) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}

三、单调栈

单调栈可以维护出一个单调的序列，因为栈内是单调的，所以也成为单调栈。
我们用序列{5,3,4,2,1}要构造一个单调递增的数列：

  1. 5入栈，栈内元素为(5),从左到右表示为栈顶到栈底
  2. 3入栈，3比当前栈顶元素(5)小，如果成为栈顶就会递减，所以5出栈3成为栈顶元素
  3. 4进栈，符合递增规律所以4成为栈顶
  4. 2进栈，3 ,4都比2大，2成为栈顶元素
  5. 1进栈，成为栈顶元素 栈内元素有 (1)

这有什么用呢？当维护单调数列的时候我们可以使用什么呢？

作用也明显：
如果我们从左边进栈便会知道第一个将要小的数是谁，这个数就是栈顶元素，栈内部是递增而且又是从左到右进入，所以说我们可以把当前要比较的元素，与栈内元素作比较直到栈顶元素为空(没有比他小的数)或者栈顶元素比他小(就继续更新，因为栈内单调递增)。
所以我们可以用获取 当前这个数为最小值的作用区间：

const int maxn=1e6+5;
ll n,m;
int st[maxn];
int pre[maxn],cur[maxn];//表示前方可以控制到多少，后方可以控制到多少。
int num[maxn];
void get_min()
{
    //维护前方
    int bg=0;
    st[0]=0;//维护最小初始为0下标
    for(int i=1;i<=n;i++)
    {
        while(bg!=0&&num[i]<=num[st[bg]]) //st中存坐标所以栈顶元素这样表示
        //这条件翻译为 只要非空并且栈顶元素比当前元素大也可以相等
            bg--;//栈顶元素就去掉一个
        pre[i]=st[bg];
        st[++bg]=i;//当前元素入栈
    }
    //维护后方
    bg=0;
    st[0]=n+1;//维护最小初始为(n+1)下标
    for(int i=n;i>=1;i--)
    {
        while(bg!=0&&num[i]<=num[st[bg]]) //st中存坐标所以栈顶元素这样表示
        //这条件翻译为 只要非空并且栈顶元素比当前元素大也可以相等
            bg--;//栈顶元素就去掉一个
        cur[i]=st[bg];
        st[++bg]=i;//当前元素入栈
    }
    //输出维护区间
    for(int i=1;i<=n;i++)
        printf("%d :[%d %d]\n",i,pre[i]+1,cur[i]-1);//因为左边初始为0，右边初始为n+1，分别减去即可
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);
    get_min();
    return 0;
}

四、总结

1.栈很多都用于匹配问题，括号匹配等。
2.单调栈用于区间维护问题，当前最小值发挥作用的区间。
3.路还长，继续加油鸭！