CodeDevil

链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1047

【题意】

在a行b列的矩阵中找一个n*n的子矩阵，使得其最大值与最小值之差最小。

a,b≤1,000

【题解】

两次单调队列

先对每一行做单调队列，求出每个格子向左延伸n格之内的最小值b1和最大值b2

再对每一列做单调队列，利用之前求出的b1和b2，可得出以每个格子为右下角的n*n的矩阵的最小值minnum和最大值maxnum

再枚举每一个右下角，比较出最小值。

【代码】

#include <iostream>

#include <cstdio>

#include <cstdlib>

using namespace std;

 

int A,B,n;

int a[1010][1010],b1[1010][1010],b2[1010][1010],maxnum[1010][1010],minnum[1010][1010],st1[1010],st2[1010];

 

int main()

{

    int top1,top2,size1,size2,i,j;

    scanf("%d%d%d",&A,&B,&n);

    for (i=1;i<=A;i++)

        for (j=1;j<=B;j++)

            scanf("%d",&a[i][j]);

    for (i=1;i<=A;i++)

    {

        top1=top2=1,size1=size2=0;

        for (j=1;j<=B;j++)

        {

            if (a[i][j]>a[i][st1[size1]] || size1==0)

                st1[++size1]=j;

            else

            {

                while (a[i][j]<=a[i][st1[size1]] && size1>=top1)

                    size1--;

                st1[++size1]=j;

            }

            if (st1[top1]<=j-n) top1++;

            if (a[i][j]<a[i][st2[size2]] || size2==0)

                st2[++size2]=j;

            else

            {

                while (a[i][j]>=a[i][st2[size2]] && size2>=top2)

                    size2--;

                st2[++size2]=j;

            }

            if (st2[top2]<=j-n) top2++;

            if (j>=n)

            {

                b1[i][j]=a[i][st1[top1]];

                b2[i][j]=a[i][st2[top2]];

            }

        }   

    }

    for (j=n;j<=B;j++)

    {

        top1=top2=1,size1=size2=0;

        for (i=1;i<=A;i++)

        {

            if (b1[i][j]>b1[st1[size1]][j] || size1==0)

                st1[++size1]=i;

            else

            {

                while (b1[i][j]<=b1[st1[size1]][j] && size1>=top1)

                    size1--;

                st1[++size1]=i;

            }

            if (st1[top1]<=i-n) top1++;

            if (b2[i][j]<b2[st2[size2]][j] || size2==0)

                st2[++size2]=i;

            else

            {

                while (b2[i][j]>=b2[st2[size2]][j] && size2>=top2)

                    size2--;

                st2[++size2]=i;

            }

            if (st2[top2]<=i-n) top2++;

            if (i>=n)

            {

                minnum[i][j]=b1[st1[top1]][j];

                maxnum[i][j]=b2[st2[top2]][j];

            }

        }

    }

    int ans=2147483647;

    for (i=n;i<=A;i++)

        for (j=n;j<=B;j++)

            ans=min(ans,maxnum[i][j]-minnum[i][j]);

    printf("%d\n",ans);

    return 0;

}