题目描述
有一个 $a \times b$ 的整数组成的矩阵,现请你从中找出一个 $n \times n$ 的正方形区域,使得该区域所有数中的最大值和最小值的差最小。
输入格式
第一行为三个整数,分别表示 $a,b,n$ 的值;
第二行至第 $a+1$ 行每行为 $b$ 个非负整数,表示矩阵中相应位置上的数。
输出格式
输出仅一个整数,为 $a \times b$ 矩阵中所有“$n \times n$ 正方形区域中的最大整数和最小整数的差值”的最小值。
数据范围
$2 \le a,b \le 1000$,
$n \le a,n \le b,n \le 100$,
矩阵中的所有数都不超过 $10^9$。
输入样例:
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
输出样例:
1
C++ 代码
/*
二维滑动窗口
先预处理出每一行中窗口内的最值,并将其存到对应正方形的最右边
在预处理出每一列中窗口内的最值,并将其存到对应正方形的最下边
则正方形的右下角存的就是最值
*/
#include <iostream>
using namespace std;
const int N = 1010, INF = 0x3f3f3f3f;
int w[N][N];
int maxv[N][N]; // 存每行的最大值
int minv[N][N]; // 存每行的最小值
int a[N], b[N], c[N], d[N]; // 存每列的最值
int q[N]; // 滑动窗口的队列
int n, m, k; // 矩形的高、宽,正方形的边长
void get_max(int t[], int f[], int n) // 一维滑动窗口求最大值
{
int hh = 0, tt = -1;
for(int i = 1;i <= n;i ++)
{
if(hh <= tt && q[hh] < i - k + 1) hh ++;
while(hh <= tt && t[q[tt]] <= t[i]) tt --;
q[++ tt] = i;
f[i] = t[q[hh]];
}
return ;
}
void get_min(int t[], int f[], int n) // 一维滑动窗口求最小值
{
int hh = 0, tt = -1;
for(int i = 1;i <= n;i ++)
{
if(hh <= tt && q[hh] < i - k + 1) hh ++;
while(hh <= tt && t[q[tt]] >= t[i]) tt --;
q[++ tt] = i;
f[i] = t[q[hh]];
}
return ;
}
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_max(w[i], maxv[i], m); // 求第 i 行的滑动窗口最大值,并记录到 maxv 中
get_min(w[i], minv[i], m); // 求第 i 行的滑动窗口最小值,并记录到 minv 中
}
int res = INF;
for(int i = k;i <= m;i ++) // 从 k 开始才算正方形
{
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 i = k;i <= n;i ++) res = min(res, c[i] - d[i]);
}
cout << res << endl;
return 0;
}