二刷提高课，题解目录在这里— 提高课的题解目录

注意处理问题的思维，原本处理kk的二维数组
我们先将其进行压缩，将每行的k个的最后一个代表这k个的核心属性
然后再将列进行压缩，于是每个点就代表了一个kk的二维矩阵
这是处理子矩阵及其巧妙地做法

#include<iostream>
using namespace std;
const int N=2010;
int n,m,k;
int w[N][N];
int rmi[N][N],rma[N][N];
int q[N];
void gtmi(int a[],int b[],int tot)
{
    int hh=0,tt=-1;
    for(int i=1;i<=tot;i++)
    {
        if(hh<=tt&&q[hh]+k<=i)hh++;
        while(hh<=tt&&a[q[tt]]>=a[i])tt--;
        q[++tt]=i;
        b[i]=a[q[hh]];
    }
}
void gtma(int a[],int b[],int tot)
{
    int hh=0,tt=-1;
    for(int i=1;i<=tot;i++)
    {
        if(hh<=tt&&q[hh]+k<=i)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++)
    scanf("%d",&w[i][j]);
    for(int i=1;i<=n;i++)
    {
        gtmi(w[i],rmi[i],m);
        gtma(w[i],rma[i],m);
    }
    int res=1e9;
    int a[N],b[N],c[N];
    for(int i=k;i<=m;i++)//行取了最大值然后取列（意义上是n范围的所以可以直接从k开始），再进行一一来枚举就能取得最大最小值
    {
        for(int j=1;j<=n;j++)a[j]=rmi[j][i];//用a来记录
        gtmi(a,b,n);
        for(int j=1;j<=n;j++)a[j]=rma[j][i];//用a来记录
        gtma(a,c,n);
        for(int j=k;j<=n;j++)
        {
            res=min(res,c[j]-b[j]);
        }
    }
    printf("%d",res);
    return 0;

}