前言(吐槽)

第一次知道这个东西,把暴力搜索的扫描法O(nm2)降成了O(nm)

有点腻害。

这玩意是国家队写的论文!作者是咱胡建银!(知网没找到,只能找到百度文库的)

浅谈用极大化思想解决最大子矩形问题-王知昆

开始学习!


传统的扫描法我就不讲了,其实就是暴力求解,直接讲悬线法算法了

算法核心

首先是对几个东西的定义:

定义

最大子矩形问题

在一个给定的矩形中有一些障碍点,找出内部不包含障碍点的,边与整个矩形平行或重合的最大子矩形。

  • 有效子矩型:满足要求的子矩形

  • 极大子矩型:无法再向外拓展的有效子矩形

  • 最大子矩型:最大的一个有效子矩形

显然有,在一个有障碍点的矩形中,最大子矩形一定是极大子矩形

悬线(其实这个挺直白的

  • 有效竖线:除了两个端点以外,不覆盖任何一个障碍点的竖直线段

  • 悬线:上端覆盖了一个障碍点或者到达整个矩形上边界的有效线段

每个悬线上的点的与底部的点一一对应,矩形中每一个点(矩形顶部点除外)都对应了一条悬线。

如果把一条悬线向左右两个方向尽可能的移动,那么就得到了一个矩形。

注意:悬线对应的矩型不一定是极大子矩阵,因为悬线定义中固定了悬线的下边界,故而,悬线左右移动所得到的矩形无法向下扩展。

算法变量

  • $height _{i, j}$ :表示以$(i,j)$为底的悬线的

  • $left _{i, j}$:表示以$(i,j)$为底的悬线向左最多能移动到的位置

  • $right _{i, j}$:表示以$(i,j)$为底的悬线向右最多能移动到的位置

初始化(预处理)

我们需要对这三个数组进行一次预处理

悬线长度预处理

显然$(i,j)$如果不是障碍点的话,$height {i, j} = height {i-1, j} +1$
否则$height _{i, j} = 1$

所以有

向左移动距离预处理(左右移动都是DP过程)

我们逐层遍历,显然在没有障碍点的情况下,$left{i,j} = left{i,j-1}$;而左边点是障碍点时显然$left_{i,j}=j$。所以有

  • $left_{i,j} = (i,j)\text{左边第一个障碍点/边界位置}+1 = (i,j-1)\text{左边第一个障碍点/边界位置}+1$

如果$(i,j)$的上一个点不是障碍点的情况时有

  • $left{i,j} = left{i-1,j}$

我们整合一下就是

向右移动距离预处理

这个和向左也是类似的,方程如下:

实际操作

因为向左预处理是$j: 0→m-1$,而向右预处理是$j: m-1→0$

原理上来讲这两个不会放到同一个for二层循环里。但取$left/right_{i-1,j}$是自顶向下,无所谓循环从左向右还是从右向左,所以取max和min我们一般放在求最大面积的循环中

预处理一般只处理$left{i,j} = left{i,j-1}$和$right{i,j} = right{i,j+1}$,以及高度的预处理,而DP的操作我们丢到求面积的过程中

面积处理

显然对于每段悬线来讲,$S{i,j} = height{i,j} * (right{i,j} - left{i,j} + 1)$

而$left/right_{i,j}$的DP过程可以放在求面积之前

所以最终处理所需时间是O(nm)


板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//预处理
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
right[i][j]=left[i][j]=j,up[i][j]=1;
for(int i=1;i<=n;i++)
for(int j=2;j<=m;j++)
if(满足条件)
right[i][j]=right[i][j-1];
for(int i=1;i<=n;i++)
for(int j=m-1;j>=1;j--)
if(满足条件)
left[i][j]=left[i][j+1];

//DP和面积处理
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(满足条件){
right[i][j]=min(right[i][j],right[i-1][j]);
left[i][j]=max(left[i][j],left[i-1][j]);
up[i][j]=up[i-1][j]+1;
}
s = max(s, up[i][j] * (right[i][j] - left[i][j] + 1));
}

题目

咕咕咕咕咕