Time Limit: 10 Sec Memory Limit: 162 MB
Description
有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值
的差最小。
Input
第一行为3个整数，分别表示a,b,n的值第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每
行相邻两数之间用一空格分隔。
100%的数据2<=a,b<=1000,n<=a,n<=b,n<=1000
Output
仅一个整数，为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。
Sample Input
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
Sample Output
1
题解
区间RMQ问题，我们用单调队列来解决。
定义X[i][j]为第i行，第j~j+n-1范围内的最大值，x[i][j]为最小值。
首先先更新出这两个数组的值，用单调队列。
再定义Y[i][j]为i~i+n-1,j~j+n-1范围内的最大值，y[i][j]为最小值，用X与x数组来更新，求出的
便是题目要求的答案。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int X[MAXN][MAXN],aa[MAXN][MAXN],n,a,b;
int x[MAXN][MAXN],Y[MAXN][MAXN],y[MAXN][MAXN];
int q[MAXN],head1,tail1,Q[MAXN],head2,tail2;
int ans=0x7fffffff;
inline void debug(){
cout<<endl;
for(int i=1;i<=a;i++){
for(int j=1;j<=b-n+1;j++)
cout<<X[i][j]<<" ";
cout<<endl;
}
cout<<endl;
for(int i=1;i<=a;i++){
for(int j=1;j<=b-n+1;j++)
cout<<x[i][j]<<" ";
cout<<endl;
}
cout<<endl;
for(int i=1;i<=a-n+1;i++){
for(int j=1;j<=b-n+1;j++)
cout<<Y[i][j]<<" ";
cout<<endl;
}
cout<<endl;
for(int i=1;i<=a-n+1;i++){
for(int j=1;j<=b-n+1;j++)
cout<<y[i][j]<<" ";
cout<<endl;
}
}
int main(){
scanf("%d%d%d",&a,&b,&n);
for(register int i=1;i<=a;i++){
head1=tail1=head2=tail2=1;q[1]=1;Q[1]=1;
for(register int j=1;j<=b;j++){
scanf("%d",&aa[i][j]);
while(aa[i][j]>=aa[i][Q[tail1]] && head1<=tail1) tail1--;
while(aa[i][j]<=aa[i][q[tail2]] && head2<=tail2) tail2--;
Q[++tail1]=j,q[++tail2]=j;
while(j-Q[head1]>=n) head1++;
while(j-q[head2]>=n) head2++;
if(j>=n) X[i][j-n+1]=aa[i][Q[head1]],x[i][j-n+1]=aa[i][q[head2]];
}
}
// debug();
for(register int i=1;i<=b-n+1;i++){
head1=tail1=head2=tail2=1;q[1]=1;Q[1]=1;
for(register int j=1;j<=a;j++){
while(X[j][i]>=X[Q[tail1]][i] && head1<=tail1) tail1--;
while(x[j][i]<=x[q[tail2]][i] && head2<=tail2) tail2--;
Q[++tail1]=j,q[++tail2]=j;
while(j-Q[head1]>=n) head1++;
while(j-q[head2]>=n) head2++;
if(j>=n) Y[j-n+1][i]=X[Q[head1]][i],y[j-n+1][i]=x[q[head2]][i];
}
}
// debug();
// cout<<ans<<endl;
for(register int i=1;i<=a-n+1;i++)
for(register int j=1;j<=b-n+1;j++)
ans=min(ans,Y[i][j]-y[i][j]);
printf("%d",ans);
return 0;
}
还有一种思路是二维ST表
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1005;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
int a,b,n,ans=1e9+1,to;
int Min[MAXN][MAXN][11],Max[MAXN][MAXN][11];
int log[MAXN];
inline void ST(){
log[0]=1;
for(register int i=1;i<=to;i++){
log[i]=log[i-1];
if(1<<log[i-1]+1==i) log[i]++;
}
for(register int k=1;k<=log[to];k++)
for(register int i=1;i<=a-(1<<k)+1;i++)
for(register int j=1;j<=b-(1<<k)+1;j++){
Min[i][j][k]=min
(min(Min[i][j][k-1],Min[i+(1<<k-1)][j][k-1]),
min(Min[i][j+(1<<k-1)][k-1],Min[i+(1<<k-1)][j+(1<<k-1)][k-1]));
Max[i][j][k]=max
(max(Max[i][j][k-1],Max[i+(1<<k-1)][j][k-1]),
max(Max[i][j+(1<<k-1)][k-1],Max[i+(1<<k-1)][j+(1<<k-1)][k-1]));
}
}
inline int work(int x,int y){
int mn=min
(min(Min[x][y][log[n]],Min[x+n-(1<<log[n])][y][log[n]]),
min(Min[x][y+n-(1<<log[n])][log[n]],Min[x+n-(1<<log[n])][y+n-(1<<log[n])][log[n]]));
int mx=max
(max(Max[x][y][log[n]],Max[x+n-(1<<log[n])][y][log[n]]),
max(Max[x][y+n-(1<<log[n])][log[n]],Max[x+n-(1<<log[n])][y+n-(1<<log[n])][log[n]]));
return mx-mn;
}
int main(){
a=rd();b=rd();n=rd();to=(min(a,b));
for(register int i=1;i<=a;i++)
for(register int j=1;j<=b;j++)
Min[i][j][0]=Max[i][j][0]=rd();
ST();
for(register int i=1;i<=a-n+1;i++)
for(register int j=1;j<=b-n+1;j++)
ans=min(ans,work(i,j));
printf("%d",ans);
return 0;
}