题目描述
有一个ab的整数组成的矩阵，现请你从中找出一个nn的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
输入输出格式
输入格式：
第一行为3个整数，分别表示a,b,n的值
第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。
输出格式：
仅一个整数，为ab矩阵中所有“nn正方形区域中的最大整数和最小整数的差值”的最小值。
输入输出样例
输入样例#1：
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
输出样例#1：
1
说明
问题规模
（1）矩阵中的所有数都不超过1,000,000,000
（2）20%的数据2<=a,b<=100,n<=a,n<=b,n<=10
（3）100%的数据2<=a,b<=1000,n<=a,n<=b,n<=100
题解
反正我一看到题就想着用ST表。。
不过后来发现还有一种更优秀的做法，那便是利用单调队列，求出一个满足一维上的最值数组
之后这个最值数组上再次利用单调队列求出二维的最值数组，便可以更优秀的时间复杂度过掉这道题（而且代码也不长）
code:(2dST表) 很好写
//By Menteur_Hxy
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define F(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
int rd() {
int x=0,f=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
return x*f;
}
const int INF=0x7fffffff;
const int MAX=1050;
int a,b,n,m;
int ma[MAX][MAX][12],mi[MAX][MAX][12];
inline int min(int a,int b) {
if(a<b) return a;
return b;
}
inline int max(int a,int b) {
if(a>b) return a;
return b;
}
void init() {
F(k,1,11) F(i,1,a-(1<<k)+1) F(j,1,b-(1<<k)+1)
mi[i][j][k]=min(min(mi[i][j][k-1],mi[i+(1<<(k-1))][j+(1<<(k-1))][k-1]),
min(mi[i+(1<<(k-1))][j][k-1],mi[i][j+(1<<(k-1))][k-1])),
ma[i][j][k]=max(max(ma[i][j][k-1],ma[i+(1<<(k-1))][j+(1<<(k-1))][k-1]),
max(ma[i+(1<<(k-1))][j][k-1],ma[i][j+(1<<(k-1))][k-1]));
}
inline int query(int i,int j) {
int maxn=-INF,minn=INF;
minn=min(min(mi[i][j][m],mi[i+n-(1<<m)][j+n-(1<<m)][m]),
min(mi[i+n-(1<<m)][j][m],mi[i][j+n-(1<<m)][m]));
maxn=max(max(ma[i][j][m],ma[i+n-(1<<m)][j+n-(1<<m)][m]),
max(ma[i+n-(1<<m)][j][m],ma[i][j+n-(1<<m)][m]));
return maxn-minn;
}
int main() {
a=rd(),b=rd(),n=rd();
F(i,1,a) F(j,1,b) ma[i][j][0]=mi[i][j][0]=rd();
init(); m=log(n)/log(2); int ans=INF;
F(i,1,a-n+1) F(j,1,b-n+1) ans=min(ans,query(i,j));
printf("%d",ans);
return 0;
}
code:(单调队列)
//By Menteur_Hxy
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define F(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
int rd() {
int x=0,f=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
return x*f;
}
const int N=1050,INF=0x7fffffff;
int n,m,k,ans=INF,h,H,T,t;
int da[N][N],X[N][N],x[N][N],Y[N][N],y[N][N],Q[N<<1],q[N<<1];
int main() {
n=rd(),m=rd(),k=rd();
F(i,1,n) F(j,1,m) da[i][j]=rd();
F(i,1,n) { H=T=h=t=Q[1]=q[1]=1;
F(j,2,m) {
while(T>=H and da[i][j]>=da[i][Q[T]]) T--;
while(t>=h and da[i][j]<=da[i][q[t]]) t--;
t++,T++; q[t]=Q[T]=j;
while(j-Q[H]>=k) H++;
while(j-q[h]>=k) h++;
if(j>=k) X[i][j-k+1]=da[i][Q[H]],x[i][j-k+1]=da[i][q[h]];
}
}
F(i,1,m-k+1) { H=T=t=h=Q[1]=q[1]=1;
F(j,2,n) {
while(T>=H and X[j][i]>=X[Q[T]][i]) T--;
while(t>=h and x[j][i]<=x[q[t]][i]) t--;
t++,T++; q[t]=Q[T]=j;
while(j-Q[H]>=k) H++;
while(j-q[h]>=k) h++;
if(j>=k) Y[j-k+1][i]=X[Q[H]][i],y[j-k+1][i]=x[q[h]][i],
ans=min(ans,Y[j-k+1][i]-y[j-k+1][i]);
}
}
return printf("%d",ans),0;
}