C++(clang++11) 解法, 执行用时: 210ms, 内存消耗: 12180K, 提交时间: 2021-03-14 13:57:29

#include<bits/stdc++.h>
using namespace std;
const int NN=1004;
int g[NN][NN],maxn[NN][NN],minn[NN][NN],q1[NN],q2[NN];
int main()
{
	int a,b,n,ans=1e9,h1,h2,t1,t2;
	scanf("%d%d%d",&a,&b,&n);
	for(int i=1;i<=a;i++)
		for(int j=1;j<=b;j++)
			scanf("%d",&g[i][j]);
	for(int i=1;i<=a;i++)
	{
		h1=0;
		h2=0;
		t1=-1;
		t2=-1;
		for(int j=1;j<=b;j++)
		{
			if(h1<=t1&&q1[h1]<=j-n)
				h1++;
			if(h2<=t2&&q2[h2]<=j-n)
				h2++;
			while(h1<=t1&&g[i][q1[t1]]<=g[i][j])
				t1--;
			while(h2<=t2&&g[i][q2[t2]]>=g[i][j])
				t2--;
			q1[++t1]=q2[++t2]=j;
			if(h1<=t1&&j>=n)
				maxn[i][j-n+1]=g[i][q1[h1]];
			if(h2<=t2&&j>=n)
				minn[i][j-n+1]=g[i][q2[h2]];
		}
	}
	for(int i=1;i<=b-n+1;i++)
	{
		h1=0;
		h2=0;
		t1=-1;
		t2=-1;
		for(int j=1;j<=a;j++)
		{
			if(h1<=t1&&q1[h1]<=j-n)
				h1++;
			if(h2<=t2&&q2[h2]<=j-n)
				h2++;
			while(h1<=t1&&maxn[q1[t1]][i]<=maxn[j][i])
				t1--;
			while(h2<=t2&&minn[q2[t2]][i]>=minn[j][i])
				t2--;
			q1[++t1]=q2[++t2]=j;
			if(h1<=t1&&h2<=t2&&j>=n)
				ans=min(ans,maxn[q1[h1]][i]-minn[q2[h2]][i]);
		}
	}
	printf("%d",ans);
	return 0;
}