题目描述

一看正方形，得，二维数组，单调队列。
单调队列可以将一个区间最大值存储，所以只需要根据给定的正方形长度先横着推一遍，再竖着推一遍，将正方形中的最大值和最小值都储存在正方形右下角方格，最后遍历即可。
先以行储存以k为长度的最大/小值；
再以剩下k-m横向长度的最值向下扩展k个长度，储存在长k宽k的矩阵右下角位置；
最后便利最小值；
例子 ： n = 5,m = 4, k = 2.

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int n,m,k,w[maxn][maxn],row_min[maxn][maxn],row_max[maxn][maxn],q[maxn*maxn];
void get_min(int a[],int b[],int c){//单调数组 储存 次数
	int head=0,tail=-1;
	for(int i=1;i<=c;i++){
		while(head<=tail&&q[head]<i-k+1)//k=2,i=5例4~5 头最多i-k+1
			head++;
		while(head<=tail&&a[q[tail]]>=a[i])
			tail--;
		q[++tail] = i;
		b[i]=a[q[head]];
	}
}
void get_max(int a[],int b[],int c){//单调数组 储存 次数
	int head=0,tail=-1;
	for(int i=1;i<=c;i++){
		while(head<=tail&&q[head]<i-k+1)
			head++;
		while(head<=tail&&a[q[tail]]<=a[i])
			tail--;
		q[++tail] = i;
		b[i]=a[q[head]];
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			scanf("%d",&w[i][j]);
		}
	for(int i=1;i<=n;i++){//扫行最值
		get_min(w[i],row_min[i],m);
		get_max(w[i],row_max[i],m);
	}
	int t[maxn],a[maxn],b[maxn];
	int res=0x3f3f3f3f;
	for(int j=k;j<=m;j++){
		for(int i=1;i<=n;i++) t[i]=row_min[i][j];//存t,向下遍历
		get_min(t, a, n);
		for(int i=1;i<=n;i++) t[i]=row_max[i][j];//存t,向下遍历
		get_max(t, b, n);

		for(int i=k;i<=n;i++){//扫列
			res=min(res,b[i]-a[i]);
		}

	}
	printf("%d",res);
	return 0;
}