题目描述

有一个 $a \times b$ 的整数组成的矩阵，现请你从中找出一个 $n \times n$ 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

输入格式

第一行为 $3$ 个整数，分别表示 $a,b,n$ 的值。

第二行至第 $a+1$ 行每行为 $b$ 个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。

输出格式

仅一个整数，为 $a \times b$ 矩阵中所有“ $n \times n$ 正方形区域中的最大整数和最小整数的差值”的最小值。

样例 #1

样例输入 #1

5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2

样例输出 #1

1

提示

问题规模。

矩阵中的所有数都不超过 $1,000,000,000$。

$20\%$ 的数据 $2 \le a,b \le 100,n \le a,n \le b,n \le 10$。

$100\%$ 的数据 $2 \le a,b \le 1000,n \le a,n \le b,n \le 100$。

题目分析

目的：求出$n\times n$矩形区域内的最大整数和最小整数的差值的最小值。

可发现重点在于如何求解矩形区间内的最值。

首先可以思考暴力方式，枚举所有的$n\times n$的矩形区间，再通过双重循环遍历矩形区域内的所有元素从而报出最值。分析该种方式的时间复杂度为$O(n^4)$ 结合本题的数据范围$2 \le a,b \le 1000,n \le a,n \le b,n \le 100$，妥妥地会超时。

思考过程中用时较长的是哪块。可发现对于矩形区间内最值的寻找采用了$O(n^2)$ 的方式，速度较慢，可以考虑在这块地方进行优化。

对于最值，存在一种“可合并”的特征。两个较小区域的最值可合并得到两个较大区间内的最值（如下图）。$maxAll=max(max1,max2)$

利用这种可合并的特征。若我们求解出若干行长度为n的连续区间的最值，再将它们进行合并，则可得到一个矩形区间的最值（如下图）。

也就是说如果要求出$n\times n$ 矩形区域内的最值我们可以

1. 先求出每一行，长度为$n$的连续区间内的最值
2. 再在上一步的基础上，求出第一步最值的每一列的长为$n$的连续区间的最值
3. 得到$n\times n$ 大小的区间最值

图示：

无论是第一步求“横”着的每一行长为$n$ 的连续区间内的最值还是第二步求“竖”着的长为 $n$的连续区间内的最值，归根到底是去求一个固定长度的连续区间最值问题 ,那么这类问题我们可以采用单调队列进行求解。每一行、列都是$O(n)$ 的复杂度。整体可以用$O(n^2)$ 的复杂度求出所有的 $n\times n$ 的矩形区间内的最值。

本题要求的是$n\times n$ 的矩形区间内的最大值 减去 最小值 的最大值，那么我们可以处理两遍，一遍求出最大值，一遍求出最小值。之后再求出所有的差值得到答案。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int a,b,n;
int c[N][N];
//max1 每一行长度为n的连续区间最大值
//max2 对max1处理，每一列长度为n的连续区间最大值。（原数列n*n区域内的最大值）
int max1[N][N],max2[N][N];
int min1[N][N],min2[N][N];//同上，为区间最小值
deque<int> q1,q2;//q1-求区间最大值的单调队列 q2 求区间最小值的单调队列
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",&c[i][j]);
        }
    }
    //求“横着”连续区间长度为n的区间最值
    for(int i=1;i<=a;i++){
        q1.clear();q2.clear();//清空
        for(int j=1;j<=b;j++){
            //单调队列 掐头去尾，求区间最大值 （单调下降）
            //将距离超过n的队首元素删除
            while(!q1.empty() && j-q1.front()+1>n) q1.pop_front();
            //将队尾<=c[i][j]的元素删除
            while(!q1.empty() && c[i][q1.back()]<=c[i][j]) q1.pop_back();
            q1.push_back(j);//将当前行第j列元素入队
            if(j>=n)//记录每一行长度为n连续区间内的最大值
                max1[i][j-n+1]=c[i][q1.front()];

            //求区间最小值 （单调上升）
            //将距离超过n的队首元素删除
            while(!q2.empty() && j-q2.front()+1>n) q2.pop_front();
            //将队尾>=c[i][j]的元素删除
            while(!q2.empty() && c[i][q2.back()]>=c[i][j]) q2.pop_back();
            q2.push_back(j);//将当前行第j列元素入队
            if(j>=n)//记录每一行长度为n连续区间内的最小值
                min1[i][j-n+1]=c[i][q2.front()];
        }
    }
    //求“竖着”连续长度为n的连续区间最值，合并为原数列n*n矩形区间内的最值
    for(int j=1;j<=b-n+1;j++){
        q1.clear();q2.clear();//清空
        for(int i=1;i<=a;i++){
            //求n*n区间最大值
            while(!q1.empty() && i-q1.front()+1>n) q1.pop_front();
            while(!q1.empty() && max1[q1.back()][j]<=max1[i][j]) q1.pop_back();
            q1.push_back(i);
            if(i>=n)
                max2[i-n+1][j]=max1[q1.front()][j];
            //求n*n区间最小值
            while(!q2.empty() && i-q2.front()+1>n) q2.pop_front();
            while(!q2.empty() && min1[q2.back()][j]>=min1[i][j]) q2.pop_back();
            q2.push_back(i);
            if(i>=n)
                min2[i-n+1][j]=min1[q2.front()][j];
        }
    }
    int ans=2e9;
    //遍历所有n*n区间最值，求差值
    for(int i=1;i<=a-n+1;i++){
        for(int j=1;j<=b-n+1;j++){
            //寻找最大差值
            ans=min(ans,max2[i][j]-min2[i][j]);
        }
    }
    cout<<ans;//输出
    return 0;
}