二维RMQ(因为蒟蒻不会单调dp和ST)：

分别记录下最大值和最小值，然后查询即可。

CODE：

#include<bits/stdc++.h>
using namespace std;
int n,m,k,ans=0x3f3f3f3f,mp[1010][1010],maxn[1010][1010],minn[1010][1010];
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(register int i=1;i<=n;++i)for(register int j=1;j<=m;++j){
        scanf("%d",&mp[i][j]);
        maxn[i][j]=mp[i][j],minn[i][j]=mp[i][j];
    }
    for(register int l=2;l<=k;++l)for(register int i=n;i>=l;i--)for(register int j=m;j>=l;j--)maxn[i][j]=max(mp[i][j],max(maxn[i-1][j],max(maxn[i][j-1],maxn[i-1][j-1]))),minn[i][j]=min(mp[i][j],min(minn[i-1][j],min(minn[i][j-1],minn[i-1][j-1])));
    for(register int i=k;i<=n;++i)for(register int j=k;j<=m;++j)ans=min(ans,maxn[i][j]-minn[i][j]);
    printf("%d",ans);
    return 0;
}

二维 st 表维护区间最大/最小值，单调队列维护即可。

时间复杂度：$O(nm \log n)$（大概是 1e7 的计算量）。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=1e3+5;
const int inf=0x7fffffff; 
int n,m,q,a[N][N];
int mx[N][N][10],mn[N][N][10],mylog[N];
int l1,r1,l2,r2;
PII Q1[N],Q2[N];
void build(){
	for(int i=1;i<=m;i++){
		mylog[i]=log2(i);
	}
	for(int r=1;r<=n;r++){
		for(int i=1;i<=m;i++){
			mx[r][i][0]=a[r][i];
			mn[r][i][0]=a[r][i];
		}
		for(int j=1;j<=10;j++){
			for(int i=1;i+(1<<j)-1<=m;i++){
				mx[r][i][j]=max(mx[r][i][j-1],mx[r][i+(1<<(j-1))][j-1]);
				mn[r][i][j]=min(mn[r][i][j-1],mn[r][i+(1<<(j-1))][j-1]);
			}
		}
	}
}
int qmax(int now,int l,int r){
	int k=mylog[r-l+1];
	return max(mx[now][l][k],mx[now][r-(1<<k)+1][k]);
}
int qmin(int now,int l,int r){
	int k=mylog[r-l+1];
	return min(mn[now][l][k],mn[now][r-(1<<k)+1][k]);
}
int main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
		}
	}
	build();
	int ans=inf;
	for(int j=1;j<=m-q+1;j++){
		l1=l2=1,r1=r2=0;
		Q1[l1]=Q2[l2]={0,0};
		for(int i=1;i<=n;i++){
			int maxn=qmax(i,j,j+q-1);
			int minn=qmin(i,j,j+q-1);
			while(l1<=r1&&maxn>=Q1[r1].second)r1--;
			while(l2<=r2&&minn<=Q2[r2].second)r2--;
			Q1[++r1]={i,maxn};
			Q2[++r2]={i,minn};
			if(i>=q){
				while(l1<=r1&&i-q>=Q1[l1].first)l1++;
				while(l2<=r2&&i-q>=Q2[l2].first)l2++;
				if(Q1[l1].second-Q2[l2].second<ans){
					ans=Q1[l1].second-Q2[l2].second;
				}
			}
		}
	}
	printf("%d",ans);
	return 0;
}

暴力求二维 RMQ，类似二维前缀和。

时间复杂度：$O(nmk)$（大概是 1e8 的计算量）。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
const int inf=0x3f3f3f3f;
int f[N][N],g[N][N];
int main(){
	int n,m,q;scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int x;scanf("%d",&x);
			f[i][j]=g[i][j]=x;
		}
	}
	for(int k=2;k<=q;k++){
		for(int i=n;i>=k;i--){
			for(int j=m;j>=k;j--){
				f[i][j]=max({f[i][j],f[i-1][j],f[i][j-1],f[i-1][j-1]});
				g[i][j]=min({g[i][j],g[i-1][j],g[i][j-1],g[i-1][j-1]});
			}
		}
	}
	int ans=inf;
	for(int i=q;i<=n;i++){
		for(int j=q;j<=m;j++){
			ans=min(ans,f[i][j]-g[i][j]);
		}
	}
	printf("%d",ans);
	return 0;
}