有一个 $a \times b$ 的整数组成的矩阵，现请你从中找出一个 $n\times n$ 的正方形区域，使得该区域所有数中的最大值和最小值的差最小，输出这个最小的差值。
链接
Luogu P2216
题解
单调队列的一道有趣的题。
事实上我们可以发现，需要找出的区域是正方形，而且大小固定，所以我们可以想到用单调队列来解决这个问题。
但这个问题是二维的，怎么把单调队列转化成二维的呢？
可以这么考虑。用 $a$ 个单调队列维护 每一行在 $[j-n+1,j]$ 的位置中的最大值和最小值。
每次我们计算正方形的最大值或最小值的时候，对于这 $a$ 个单调队列中的最大值或者最小值，我们新开一个单调队列，其中维护在 $a$ 个单调队列中 $[i-n+1,i]$ 这个范围里的最大值或者最小值。然后就可以用最大值减去最小值，并尝试更新答案。
可以证明，复杂度是 $O(n^2)$ 的。
实在偷懒，单调队列用了 $deque$ ，不开O2极慢。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include <cstdio>
#include <queue>
#include <cctype>
#include <algorithm>
#define pp pair<int,int>
using namespace std;
const int MAXN = 1100;
namespace fast_io {
//...
}using namespace fast_io;
int n,m,k;
int num[MAXN][MAXN];
deque<pp> max1[MAXN],min1[MAXN];
deque<pp> max2,min2;
void init(){
read(n),read(m),read(k);
for(int i = 1;i<=n;i++)
for(int j = 1;j<=m;j++)
read(num[i][j]);
}
void solve(){
int ans = 0x3f3f3f3f;
static int minn[MAXN],maxn[MAXN];
int tmin,tmax;
for(int i = 1;i<=n;i++){
//printf("i %d:\n",i);
for(int j = 1;j<=m;j++){
//max
while(!max1[j].empty()&&max1[j].begin()->second < num[i][j])
max1[j].pop_front();
max1[j].emplace_front(i,num[i][j]);
while(!max1[j].empty()&&max1[j].rbegin()->first <= i-k)
max1[j].pop_back();
tmax = max1[j].rbegin()->second;
maxn[j] = tmax;
//min
while(!min1[j].empty()&&min1[j].begin()->second > num[i][j])
min1[j].pop_front();
min1[j].emplace_front(i,num[i][j]);
while(!min1[j].empty()&&min1[j].rbegin()->first <= i-k)
min1[j].pop_back();
tmin = min1[j].rbegin()->second;
minn[j] = tmin;
}
max2.clear(),min2.clear();
for(int j = 1;j<=m;j++){
//max
while(!max2.empty()&&max2.begin()->second < maxn[j])
max2.pop_front();
max2.emplace_front(j,maxn[j]);
while(!max2.empty()&&max2.rbegin()->first <= j-k)
max2.pop_back();
tmax = max2.rbegin()->second;
//min
while(!min2.empty()&&min2.begin()->second > minn[j])
min2.pop_front();
min2.emplace_front(j,minn[j]);
while(!min2.empty()&&min2.rbegin()->first <= j-k)
min2.pop_back();
tmin = min2.rbegin()->second;
if(i>=k && j>=k)//保证解合法
ans = min(tmax-tmin,ans);
}
}
printf("%d\n",ans);
}
int main(){
init();
solve();
return 0;
}
|
