单调队列

单调队列是一种在直觉上很容易想到的数据结构。有一个经典例子是滑动窗口问题，对于一串数字（长为n），存在一个在其上滑动的矩形窗（长为k），要求线性时间内求出每个窗口中的最大值。我们可以想见在窗口的每次右移后，新的最大值与原最大值会具有很密切的关系。我们可以设置一个单调减队列q，添加元素时从队尾添加，遇到比这个元素小的，全部剔除，因为这些元素既没有新元素大，位置又靠前，它们已经失去了“出场机会”。如果发现队首元素已不在窗中（入队过早），则将其弹出。

在牛客2019暑期多校第三场中，F题运用了这一算法。

牛客暑期训练样题

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

const int N=501;
int t;
int n,m;
int mn[N],mx[N];
int a[N][N];
int q1[N],q2[N];

int main(){
    cin>>t;
    while(t--){
        int ans=1;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                scanf("%d",&a[i][j]);
            }
        }
        for(int i=1;i<=n;i++){
            memset(mx,0,sizeof(mx));
            memset(mn,0x3f,sizeof(mn));
            for(int j=i;j<=n;j++){
                int h1=0,t1=0,h2=0,t2=0;
                for(int k=1, p=0;k<=n;k++){
                    mx[k]=max(mx[k],a[j][k]);
                    mn[k]=min(mn[k],a[j][k]);

                    while(h1<t1&&mx[q1[t1-1]]<mx[k])
                        t1--;
                    while(h2<t2&&mn[q2[t2-1]]>mn[k])
                        t2--;

                    q1[t1++]=k;
                    q2[t2++]=k;

                    while(h1<t1&&h2<t2&&mx[q1[h1]]-mn[q2[h2]]>m){
                        if(q1[h1]>q2[h2])
                            p=q2[h2++];
                        else
                            p=q1[h1++];
                    }
                    ans=max(ans,(j-i+1)*(k-p));
                }
            }
        }
        cout<<ans<<endl;
    }
}