有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

参考：

单调队列好题，充分体现了我有多菜。

先维护每列长度为n的最大值/最小值，显然可以单调队列维护出来。

然后利用上面的数据再单调队列重新维护一遍就可以得到答案了。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int N=1e3+5;inline int read(){    int X=0,w=0;char ch=0;    while(ch<'0'||ch>'9'){w|=ch=='-';ch=getchar();}    while(ch>='0'&&ch<='9')X=(X<<3)+(X<<1)+(ch^48),ch=getchar();    return w?-X:X;}int a,b,n,g[N][N],t[N][N];int re[2][N][N],q[N][2];void solve(int k){    for(int i=1;i<=a;i++){    int l=0,r=0;    for(int j=1;j<=b;j++){        while(l
          
           =n)l++; if(!k)while(l
           
            =q[r-1][0])r--; else while(l
            
             <=q[r-1][0])r--; q[r][0]=t[i][j];q[r++][1]=j; g[i][j]=q[l][0]; } } for(int j=n;j<=b;j++){ int l=0,r=0; for(int i=1;i<=a;i++){ while(l
             
              =n)l++; if(!k)while(l
              
               =q[r-1][0])r--; else while(l
               
                <=q[r-1][0])r--; q[r][0]=g[i][j];q[r++][1]=i; re[k][i][j]=q[l][0]; } }}int main(){ a=read(),b=read(),n=read(); for(int i=1;i<=a;i++){ for(int j=1;j<=b;j++){ t[i][j]=read(); } } solve(0);solve(1); int ans=1e9; for(int i=n;i<=a;i++){ for(int j=n;j<=b;j++){ ans=min(ans,re[0][i][j]-re[1][i][j]); } } printf("%d\n",ans); return 0;}
               
              
             
            
           
          
         
        
       
      
     

+++++++++++++++++++++++++++++++++++++++++++

 +本文作者：luyouqi233。 　　　　　　　　　　　　　　+

 +欢迎访问我的博客：+

+++++++++++++++++++++++++++++++++++++++++++