第十三届蓝桥杯JavaB组省赛F题——最大子矩阵 (AC)
目录
- 1.统计子矩阵
- 1.问题描述
- 2.输入格式
- 3.输出格式
- 4.样例输入
- 5.样例输出
- 6.数据范围
- 7.原题链接
- 2.解题思路
- 3.Ac_code
1.统计子矩阵
1.问题描述
小明有一个大小为
N
×
M
N × M
N×M 的矩阵,可以理解为一个
N
N
N 行
M
M
M 列的二维数组。我们定义一个矩阵
m
m
m 的稳定度
f
(
m
)
f(m)
f(m) 为
f
(
m
)
=
m
a
x
(
m
)
−
m
i
n
(
m
)
f(m) = max(m) − min(m)
f(m)=max(m)−min(m),其中
m
a
x
(
m
)
max(m)
max(m)
表示矩阵
m
m
m 中的最大值,
m
i
n
(
m
)
min(m)
min(m) 表示矩阵
m
m
m 中的最小值。现在小明想要从这个矩阵中找到一个稳定度不大于
l
i
m
i
t
limit
limit 的子矩阵,同时他还希望这个子矩阵的面积越大越好(面积可以理解为矩阵中元素个数)。
子矩阵定义如下:从原矩阵中选择一组连续的行和一组连续的列,这些行列交点上的元素组成的矩阵即为一个子矩阵。
2.输入格式
第一行输入两个整数
N
,
M
N,M
N,M,表示矩阵的大小。
接下来
N
N
N 行,每行输入
M
M
M 个整数,表示这个矩阵。
最后一行输入一个整数
l
i
m
i
t
limit
limit,表示限制。
3.输出格式
输出一个整数,分别表示小明选择的子矩阵的最大面积。
4.样例输入
3 4
2 0 7 9
0 6 9 7
8 4 6 4
8
5.样例输出
6
6.数据范围
1
≤
n
≤
80
,
1
≤
m
≤
1
0
5
,
1
≤
n
∗
m
≤
1
0
5
1\leq n \leq80,1 \leq m \leq10^5,1 \leq n*m \leq10^5
1≤n≤80,1≤m≤105,1≤n∗m≤105
0
≤
0 \leq
0≤ 矩阵元素值,
l
i
m
i
t
≤
1
0
5
limit \leq 10^5
limit≤105
7.原题链接
统计子矩阵
2.解题思路
- ( 1 ) (1) (1)题意比较简单,确定一个矩阵,只需要确定左上端点和右下端点,自然而然想到一个最朴素最暴力想法——去枚举两个端点。很显然这样的复杂度是 O ( n 2 m 2 β ( t ) ) O(n^2m^2 \beta(t)) O(n2m2β(t)),其中 β ( t ) \beta(t) β(t)是判断每个矩阵所需要的时间,设该矩阵的长为 x x x,宽为 y y y ,则 β ( t ) = x ∗ y \beta(t)=x*y β(t)=x∗y。但很明显这样的思路是超时的,光是 m 2 m^2 m2 的复杂度就是我们无法接受的。
-
(
2
)
(2)
(2)假设一个矩阵的左上端点的坐标为
(
x
1
,
y
1
)
(x_1,y_1)
(x1,y1),右下坐标的端点为
(
x
2
,
y
2
)
(x_2,y_2)
(x2,y2)。仔细观察数据范围可以发现,
n
n
n 非常小,这意味着我们可以暴力枚举两点的横坐标
x
1
x_1
x1 和
x
2
x_2
x2,这样做的复杂度为
n
2
n^2
n2。这样处理后,意味着我们只需要在这个下图中的红轴和橙轴各找到一个点,也就是找到
y
1
y1
y1 和
y
2
y2
y2 ,使得矩阵的稳定度是不大于
l
i
m
i
t
limit
limit,我们先不考虑如何枚举
y
1
y1
y1和
y
2
y2
y2这个问题,先考虑对于一个确定的矩阵,如何高效的算出它的
β
(
t
)
\beta(t)
β(t)。
-
(
3
)
(3)
(3)对于一个矩阵,并没有一个高效求出它的
m
a
x
max
max以及
m
i
n
min
min的算法 ,但如果是一个一维数组,求区间的最值就有许多方法,比如
s
t
st
st表,线段树、单调队列等。我们不禁去思考,能否将一个二维矩阵处理为一维?
显然这是可行的!
假设对于一个下面的二维矩阵,设宽为 y y y,高为 x x x ,暴力求最值的复杂度是 O ( x y ) O(xy) O(xy)
如果我们可以先处理得到每一列的最值,并将其放到该列的末尾,那么对于该矩阵的最值,我们只需要考虑最后一行即可。
如图每个红色都格子都是该列的最值 ( m a x / m i n ) (max/min) (max/min),那么当我们需要求解该矩阵的最大值或者最小值时,复杂度都将只和矩阵的宽度有关,时间复杂度将会是 O ( y ) O(y) O(y)。
( 4 ) (4) (4)当然如何预处理是一个关键,我们生成两个数组 m a x [ k ] [ i ] [ j ] max[k][i][j] max[k][i][j]以及 m i n [ k ] [ i ] [ j ] min[k][i][j] min[k][i][j],其中 m a x [ k ] [ i ] [ j ] max[k][i][j] max[k][i][j]代表的含义是在第 k k k列中,第 i i i 个元素到第 j j j 个的元素最大值是多少, m i n min min数组同理。我们预处理的转移式子应该为:
m a x [ k ] [ i ] [ j ] = m a x ( m a x [ k ] [ i ] [ j − 1 ] , m a x [ k ] [ j ] [ j ] ) ; max[k][i][j] =max(max[k][i][j - 1], max[k][j][j]); max[k][i][j]=max(max[k][i][j−1],max[k][j][j]);
这个式子的含义也很简单,对于区间 [ i , j ] [i,j] [i,j]的最大值应该是 [ i , j − 1 ] [i,j-1] [i,j−1]的最大值和 j j j 位值取较大值。
由于我们处理的是每一列,这样时间复杂度是 O ( n 2 ) O(n^2) O(n2),由于总共有 m m m,所以总时间复杂度应该是 O ( n 2 m ) O(n^2m) O(n2m),这是完全可接受的。这样我们就完成了这道题第一个难点的跨越。
这一步的操作可以这样理解:
有一个部落,它有 m m m个村庄,每次村庄都有 n n n个人,每次我们需要去找到一堆村庄内最强的那个人,如果每次计算最坏都有可能是 O ( n m ) O(nm) O(nm)的复杂度,那么不如先让每个村庄自己内部打一架,派出一个最强代表,每次我们只需要让代表打一架就好了,这样复杂度就只是 O ( m ) O(m) O(m) - ( 5 ) (5) (5)现在让我们再回到之前的一个问题,确定了 x 1 x1 x1和 x 2 x2 x2的情况下,如何去确定 y 1 y1 y1和 y 2 y2 y2呢,如果同样暴力枚举的话复杂度是 O ( m 2 ) O(m^2) O(m2)不可接受。在这里我们可以巧妙地进行二分答案。因为本质上横坐标 x x x确定的是矩阵高,而 y y y确定的是矩阵的宽,我们去二分宽度——矩阵内是否存在宽度为 l l l 的矩阵稳定度不大于 l i m i t limit limit。
-
(
6
)
(6)
(6)既然可以二分,那就一定要分析其是否具有二段性,明显是有的。如果存在一个宽度为
l
l
l 的矩阵符合要求,那么一定能找到一个宽度在区间
[
1
,
l
−
1
]
[1,l-1]
[1,l−1]的矩阵也符合要求。这也非常好证明:对于下图
假设红色矩阵的值域为 [ l , r ] [l,r] [l,r],且 r − l < = l i m i t r-l<=limit r−l<=limit,说明该矩阵是稳定矩阵。因为橙色、蓝色、黄色矩阵都是红色的子矩阵,说明它的值域一定也是在 [ l , r ] [l,r] [l,r],那么说明它们也一定是稳定矩阵,到此可以说明二分的正确性。本题的第二个难点就此解决。 -
(
7
)
(7)
(7)当然既然二分当然要说明
c
h
e
c
k
check
check 函数的逻辑,当二分的值为
m
i
d
mid
mid时,也就是需要去判断是否存在宽度为
m
i
d
mid
mid的矩阵符合要求,因为我们前面预处理已经将高度压缩为
1
,所以这其实就是一个一维数组滑动窗口求最值问题,属于是单调队列的模板使用,求出每个长度为 m i d mid mid的窗口的最大值 m a x max max和最小值 m i n min min,只要有一个窗口符合 m a x − m i n < = l i m i t max-min<=limit max−min<=limit我们都返回true
,否则返回false
。 - ( 8 ) (8) (8)当二分得到最长宽度为 r r r 时,该矩阵的面积就为 ( x 2 − x 1 + 1 ) ∗ r (x2-x1+1)*r (x2−x1+1)∗r,每次用一个全局变量更新答案。考虑时间复杂度——枚举横坐标为 O ( n 2 ) O(n^2) O(n2),二分的复杂度为 O ( l o g m ) O(logm) O(logm),每次 c h e c k check check判定的复杂度是 O ( m ) O(m) O(m),所以整体时间复杂度为 O ( n 2 m l o g m ) O(n^2mlogm) O(n2mlogm)。
3.Ac_code
import java.io.*;
import java.util.*;
public class 统计子矩阵 {
//max[k][i][j]表示第k列中[i,j]之间的最大值
static int[][][] max;
static int[][][] min;
static int n, m, limit,ans;
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
String[] s=br.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
max=new int[m+1][n+1][n+1];
min=new int[m+1][n+1][n+1];
for (int i = 1; i <= n; i++) {
s=br.readLine().split(" ");
for (int j = 1; j <= m; j++) {
max[j][i][i] = min[j][i][i] = Integer.parseInt(s[j-1]);
}
}
limit = Integer.parseInt(br.readLine());
//预处理 复杂度 n^2*m
for (int k = 1; k <= m; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
max[k][i][j] = Math.max(max[k][i][j - 1], max[k][j][j]);
min[k][i][j] = Math.min(min[k][i][j - 1], min[k][j][j]);
}
}
}
for (int x1 = 1; x1 <= n; x1++) {
for (int x2 = x1; x2 <= n; x2++) {
int l = 1, r = m;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(x1, x2, mid)) l = mid;
else r = mid - 1;
}
if (check(x1,x2,r)) ans=Math.max(ans,(x2-x1+1)*r);
}
}
out.println(ans);
out.flush();
}
//k是窗口大小
static boolean check(int x1, int x2, int k) {
Deque<Integer> qmax = new ArrayDeque<>();
Deque<Integer> qmin = new ArrayDeque<>();
for (int i = 1; i <= m; i++) {
//处理最小
if (!qmin.isEmpty() && qmin.peekFirst() < i - k + 1) qmin.pollFirst();
while (!qmin.isEmpty() && min[qmin.peekLast()][x1][x2] > min[i][x1][x2]) qmin.pollLast();
qmin.offerLast(i);
//处理最大
if (!qmax.isEmpty() && qmax.peekFirst() < i - k + 1) qmax.pollFirst();
while (!qmax.isEmpty() && max[qmax.peekLast()][x1][x2] < max[i][x1][x2]) qmax.pollLast();
qmax.offerLast(i);
//说明窗口为k
if (i >= k && max[qmax.peekFirst()][x1][x2] - min[qmin.peekFirst()][x1][x2] <= limit) return true;
}
return false;
}
}