$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$
思路:
1. 枚举每一行,对于这一行,将最值放入滑动窗口的最右边
2. 枚举每一列,对于这一列,将最值放入滑动窗口的最下边
3. 如此一来,k * k 的正方形的最值就在右下角,res = min{c[j] - b[j]} (k <= j <= n)
完整代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m,k;
int w[N][N];
int row_min[N][N],row_max[N][N];
int q[N];
//将最小值放到滑动窗口的最右边
void get_min(int a[],int b[],int tot)
{
int hh=0,tt=0;
for(int i=1;i<=tot;i++)
{
if(q[hh]<i-k+1) hh++;
while(hh<=tt&&a[q[tt]]>=a[i]) tt--;
q[++tt]=i;
b[i]=a[q[hh]];
}
}
//将最大值放到滑动窗口的最右边
void get_max(int a[],int b[],int tot)
{
int hh=0,tt=0;
for(int i=1;i<=tot;i++)
{
if(q[hh]<i-k+1) hh++;
while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
q[++tt]=i;
b[i]=a[q[hh]];
}
}
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],row_min[i],m);
get_max(w[i],row_max[i],m);
}
int a[N],b[N],c[N],res=1e9;
for(int i=k;i<=m;i++) //枚举每一列
{
//将最值放到滑动窗口的最下边
for(int j=1;j<=n;j++) a[j]=row_min[j][i];
get_min(a,b,n);
for(int j=1;j<=n;j++) a[j]=row_max[j][i];
get_max(a,c,n);
//如此一来,k * k 的正方形的最值就在右下角
for(int j=k;j<=n;j++) res=min(res,c[j]-b[j]);
}
cout<<res<<endl;
return 0;
}