1. 分步做，把矩形区的最值先按行压缩到到一格存储，后按列压缩到一格存储

2. 枚举行，横向滑动窗口，把每行的窗口最值存储在 maxv[i][j], minv[i][j]

3. 枚举列，竖向滑动窗口，把每列的窗口最值存储在 c[i], d[i]

#include<iostream>
using namespace std;

const int N=1010;
int n,m,k;
int w[N][N],minv[N][N],maxv[N][N]; //maxv[i][j]:第i行,j-k+1~j列的最大值
int q[N],a[N],b[N],c[N],d[N];      //a[i]:第i行,j-k+1~j列的最大值
                                   //c[i]:第i-k+1~i行,j-k+1~j列的最大值

void get_max(int a[],int b[],int m){
  for(int i=1,h=1,t=0; i<=m; i++){
    while(h<=t && q[h]<i-k+1) h++;
    while(h<=t && a[q[t]]<=a[i]) t--;
    q[++t]=i;
    b[i]=a[q[h]];
  }
}
void get_min(int a[],int b[],int m){
  for(int i=1,h=1,t=0; i<=m; i++){
    while(h<=t && q[h]<i-k+1) h++;
    while(h<=t && a[q[t]]>=a[i]) t--;
    q[++t]=i;
    b[i]=a[q[h]];
  }
}
int main(){
  scanf("%d%d%d",&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++){ //枚举行
    get_max(w[i],maxv[i],m); //横滑窗口  
    get_min(w[i],minv[i],m);
  }
  
  int res=1e9;
  for(int j=k; j<=m; j++){ //枚举列
    for(int i=1; i<=n; i++) a[i]=maxv[i][j],b[i]=minv[i][j];
    get_max(a,c,n); //竖滑窗口
    get_min(b,d,n);
    for(int i=k;i<=n;i++) res=min(res,c[i]-d[i]);
  }
  printf("%d\n",res);
}

https://blog.csdn.net/tenkuo/article/details/153720137

邹丞治代码：

include <bits/stdc++.h>
using namespace std;
const int N=1010;
int A,B,n;
int a[N][N];
int q[N],l,r;
int mxr[N][N],mnr[N][N],mx[N][N],mn[N][N];
int main() {
    scanf("%d%d%d",&A,&B,&n);
    for(int i=1;i<=A;i++) {
        for(int j=1;j<=B;j++) {
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=1;i<=A;i++) {
        l=1,r=0;
        for(int j=1;j<=B;j++) {
            while(l<=r&&a[i][q[r]]<=a[i][j]) r--;
            q[++r]=j;
            while(l<=r&&q[l]<=j-n) l++;
            if(j>=n) mxr[i][j]=a[i][q[l]];
        }
        l=1,r=0;
        for(int j=1;j<=B;j++) {
            while(l<=r&&a[i][q[r]]>=a[i][j]) r--;
            q[++r]=j;
            while(l<=r&&q[l]<=j-n) l++;
            if(j>=n) mnr[i][j]=a[i][q[l]];
        }
    }
    for(int j=n;j<=B;j++) {
        l=1,r=0;
        for(int i=1;i<=A;i++) {
            while(l<=r&&mxr[q[r]][j]<=mxr[i][j]) r--;
            q[++r]=i;
            while(l<=r&&q[l]<=i-n) l++;
            if(i>=n) mx[i][j]=mxr[q[l]][j];
        }
        l=1,r=0;
        for(int i=1;i<=A;i++) {
            while(l<=r&&mnr[q[r]][j]>=mnr[i][j]) r--;
            q[++r]=i;
            while(l<=r&&q[l]<=i-n) l++;
            if(i>=n) mn[i][j]=mnr[q[l]][j];
        }
    }
    int ans=1<<30;
    for(int i=n;i<=A;i++) {
        for(int j=n;j<=B;j++) {
            ans=min(ans,mx[i][j]-mn[i][j]);
        }
    } 
    printf("%d",ans);
    return 0;
}