二维滑动窗口(求矩阵框内最值问题)
#include <bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f
using namespace std;
const int N=1e3+10;
int n,m,ans,k;
int q[N];
int w[N][N],maxv[N][N],minv[N][N];
int a[N],b[N],c[N],d[N];
//求出每一行滑动窗口内最大值
void get_max(int a[],int f[],int m) {
int h=0,t=-1;//注意从-1开始因为f[1]=a[1]所以q[0]=1
for(int i=1; i<=m; i++) {
while(h<=t&&q[h]+k<=i)h++;
while(h<=t&&a[i]>=a[q[t]])t--;
q[++t]=i;
f[i]=a[q[h]];
}
}
//求出每一行滑动窗口内最小值
void get_min(int a[],int f[],int m) {
int h=0,t=-1;
for(int i=1; i<=m; i++) {
while(h<=t&&q[h]+k<=i)h++;
while(h<=t&&a[i]<=a[q[t]])t--;
q[++t]=i;
f[i]=a[q[h]];
}
}
int main() {
cin>>n>>m>>k;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) cin>>w[i][j];
//在每一行做滑动窗口
for(int i=1; i<=n; i++) {
get_min(w[i],minv[i],m);
get_max(w[i],maxv[i],m);
}
ans=INF;
//处理每一列，每一个框内答案
for(int i=k; i<=m; i++) { //每一列
for(int j=1; j<=n; j++) { //每一行
a[j]=maxv[j][i];
b[j]=minv[j][i];
}
//在每一列做滑动窗口,求出每一列的最值,这样右下角为框内最值
get_max(a,c,n);
get_min(b,d,n);
for(int j=k; j<=n; j++)ans=min(c[j]-d[j],ans);
}
cout<<ans<<endl;
return 0;
}