单调栈学习笔记

文章目录
  1. 1. 作用
  2. 2. 实现
  3. 3. 具体代码
  4. 4. 例题
    1. 4.1. 代码

[原创,转载请附网址:http://dongshuyan.top]

作用

    利用单调栈,我们可以以O(n)的复杂度快速求解在a[1]~a[n]中每一个元素向某一个方向上的最长递减(或非递减等)区间长度。

实现

    a[i] :第i个元素值
    st :为单调队列
    L[i] :为对于第i个元素,其向某个方向的最长递减(非递减)元素的下标。
    下面以向左非递减为例:
    建立单调队列st,对于从1开始每个元素进栈(由于是向左所以从左向右遍历):
        1) 若原来栈空,则直接进栈。
        L[i]=1(1表示对于i个元素,从他一直到第1个元素都是每递减的)
        st[top++]=a[i];
        2) 若原来栈不空,且栈顶元素st[top]>a[i],则说明即使加入a[i],对于i来说,其向左依旧是非递减。所以直接进栈。(注意:若要非递减,则不可以带等号!若要严格递减,则带等号,可以手动试)
        L[i]=st[top]+1;
        st[top++]=a[i];
        3) 若原来栈不空,且栈顶元素st[top]<=a[i],则一直出栈到满足st[top]>a[i]或者栈为空为止,因为这样才能保证对于a[i],其要找的是向左不递减。
        while (top>0 && a[st[top-1]]>=a[j]) top–;
        l[j]=top==0?1:(st[top-1]+1);
        st[top++]=j;

具体代码

int t=0;
for (int j=1;j<=n;j++) 
{
    while (t>0 && a [st[t-1]]>=a [j]) t--;
    l[j]=t==0?1:(st[t-1]+1);
    st[t++]=j;
}

例题

HDU2870:
    题目地址: Largest Submatrix
    题目大意:
有个字母矩阵,包含字母”a、b、c、w、x、y、z”,其中,w能变为”a、b”,x能变为”b、c”,y能变为”a、c”,z能变为”a、b、c”。问能构成的最大字母完全一样的子矩阵面积为多大?
    解题思路:
将全部字符依次转化a, b, c, 再分别求出这三个矩阵的最大子矩阵即可.于是, 问题转化为求矩阵中最大的子矩阵了.
  设置一个变量Num[][]记录位置的最大高度, Num[i][j]表示Matritx[i][j]位置上的最大高度。
  这样, 只要枚举以各个Num[i][j]为矩阵最小高度, 分别向前后推进扩展矩阵, 如果Num[i][j + 1] >= Num[i][j]则可以向前扩展, 同理Num[i][j - 1] >= Num[i][j]则可以向后扩展, 用L[j], R[j]分别表示当前位置 j 向前向后扩展的最大位置
剩下单调队列求L[j]、R[j]。

代码

#include <cstdio>
int n,m,ans;
char ch;
char aa[3][1005][1005]={0};
int a[3][1005][1005]={0};
int l[1005]={0};
int r[1005]={0};
int st[1005]={0};//栈 
int main()
{
    while (scanf("%d%d",&m,&n)!=EOF)
    {
        getchar();
        ans=0;
        for (int i=1;i<=m;i++)
        {
            for (int j=1;j<=n;j++)
            {
                scanf("%c",&ch);
                aa[0][i][j]=ch;
                aa[1][i][j]=ch;
                aa[2][i][j]=ch;
                if (ch=='w' || ch=='y' || ch=='z') aa[0][i][j]='a';
                if (ch=='w' || ch=='x' || ch=='z') aa[1][i][j]='b';
                if (ch=='x' || ch=='y' || ch=='z') aa[2][i][j]='c';
            }
            getchar();
        }

        for (int i=1;i<=m;i++)
            for (int j=1;j<=n;j++)
                for (int k=0;k<3;k++)
                {
                    if (aa[k][i][j]=='a'+k)
                        a[k][i][j]=a[k][i-1][j]+1;
                    else a[k][i][j]=0;
                }


        for (int k=0;k<3;k++)
        for (int i=1;i<=m;i++)
        {            
            int t=0;
            for (int j=1;j<=n;j++) 
            {
                while (t>0 && a[k][i][st[t-1]]>=a[k][i][j]) t--;
                l[j]=t==0?1:(st[t-1]+1);
                st[t++]=j;
            }

            t=0;
            for (int j=n;j>=1;j--) 
            {
                while (t>0 && a[k][i][st[t-1]]>=a[k][i][j]) t--;
                r[j]=t==0?n:(st[t-1]-1);
                st[t++]=j;
                if (ans<a[k][i][j]*(r[j]-l[j]+1)) ans=a[k][i][j]*(r[j]-l[j]+1);
            }

        }
        printf("%d\n",ans);
    }
    return 0;
}