强烈推荐这道单调队列好题！
传送门：GO
参考了一下这篇题解：GO
对于点(i,j)
两个单调队列，先以行为单位，求出长度为n的一段区间的最值(i,(j~j+n-1))，在此基础上，以列为单位，求出((i~i+n-1),(j~j+n-1))的最值。
以n为3为例：
先是这样的感觉，每个色条处理的是每块的最值。
接着根据上面求出的结果，竖着来一次。
最后就能得到每个点为左上角的n*n正方形的最值了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int read(){ 4 int x=0,f=1; 5 char c=getchar(); 6 while(!isdigit(c)){ 7 if(c=='-') f=-1; 8 c=getchar(); 9 } 10 while(isdigit(c)){ 11 x=(x<<1)+(x<<3)+(c^48); 12 c=getchar(); 13 } 14 return x*f; 15 } 16 const int N=1e3+10; 17 int a,b,n; 18 int ma[N][N]; 19 int maxwh[N][N],maxn[N][N],minwh[N][N],minn[N][N]; 20 int que1[N<<1],que2[N<<1]; 21 int head1,tail1,head2,tail2; 22 int main(){ 23 a=read();b=read();n=read(); 24 for(int i=1;i<=a;i++){ 25 for(int j=1;j<=b;j++){ 26 ma[i][j]=read(); 27 } 28 } 29 for(int i=1;i<=a;i++){ 30 head1=tail1=head2=tail2=que1[1]=que2[1]=1; 31 for(int j=2;j<=b;j++){ 32 while(head1<=tail1&&ma[i][j]>=ma[i][que1[tail1]]) tail1--; 33 while(head2<=tail2&&ma[i][j]<=ma[i][que2[tail2]]) tail2--; 34 que1[++tail1]=j; 35 que2[++tail2]=j; 36 while(j-que1[head1]+1>n) head1++; 37 while(j-que2[head2]+1>n) head2++; 38 if(j>=n) maxwh[i][j-n+1]=ma[i][que1[head1]],minwh[i][j-n+1]=ma[i][que2[head2]]; 39 } 40 } 41 for(int i=1;i<=b-n+1;i++){ 42 head1=tail1=head2=tail2=que1[1]=que2[1]=1; 43 for(int j=2;j<=a;j++){ 44 while(head1<=tail1&&maxwh[j][i]>=maxwh[que1[tail1]][i]) tail1--; 45 while(head2<=tail2&&minwh[j][i]<=minwh[que2[tail2]][i]) tail2--; 46 que1[++tail1]=j; 47 que2[++tail2]=j; 48 while(j-que1[head1]+1>n) head1++; 49 while(j-que2[head2]+1>n) head2++; 50 if(j>=n) maxn[j-n+1][i]=maxwh[que1[head1]][i],minn[j-n+1][i]=minwh[que2[head2]][i]; 51 } 52 } 53 int ans=1e9; 54 for(int i=1;i<=a-n+1;i++){ 55 for(int j=1;j<=b-n+1;j++){ 56 ans=min(ans,maxn[i][j]-minn[i][j]); 57 } 58 } 59 printf("%d",ans); 60 return 0; 61 }