这道题我们可以将每一行的滑动窗口求出来 然后统一放在窗口的最后一个位置 最后进行列的滑动窗口压缩 最大值最小值分别做一次 遍历一遍预处理出的最大值和最小值数组 更新答案即可
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
const int N=1010;
int n,m,k,a[N][N],ans_min[N][N],ans_max[N][N];
void getmin(int a[],int b[],int n){
deque<int>q;
for(int i=1;i<=n;i ){
if(!q.empty()&&i-q.front()>=k)q.pop_front();
while(!q.empty()&&a[q.back()]>=a[i])q.pop_back();
q.push_back(i);
b[i]=a[q.front()];
}
}
void getmax(int a[],int b[],int n){
deque<int>q;
for(int i=1;i<=n;i ){
if(!q.empty()&&i-q.front()>=k)q.pop_front();
while(!q.empty()&&a[q.back()]<=a[i])q.pop_back();
q.push_back(i);
b[i]=a[q.front()];
}
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i ){
for(int j=1;j<=m;j )scanf("%d",&a[i][j]);
}
for(int i=1;i<=n;i ){
getmin(a[i],ans_min[i],m),getmax(a[i],ans_max[i],m);
/*for(int j=1;j<=m;j ){
cout<<ans_min[i][j]<<" ";
}
cout<<endl;*/
}
int ans=INT_MAX,tepa[N],tarb[N],tarc[N];
for(int i=k;i<=m;i ){
for(int j=1;j<=n;j ){
tepa[j]=ans_min[j][i];
}
getmin(tepa,tarb,n);
for(int j=1;j<=n;j ){
tepa[j]=ans_max[j][i];
}
getmax(tepa,tarc,n);
for(int j=k;j<=n;j )ans=min(ans,tarc[j]-tarb[j]);
}
cout<<ans<<endl;
}
