【学习笔记】最大子矩形问题

问题类型

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


定义

有效子矩形:内部不含障碍点的、边与整个矩形平行或重合的最大子矩形。
极大子矩形:各边都与障碍点或整个矩形的边重合的有效子矩形。
最大子矩形:最大的有效子矩形。

最大子矩形 $\subseteq$ 极大子矩形 $\subseteq$ 有效子矩形


解决方案

采用 极大化思想

枚举所有极大子矩形,找到最大子矩形。

设矩形为 $n\times m$,障碍点数为 $s$。

算法一

时间复杂度 O( $s^2$ ),空间复杂度 O( $s$ )

思路

首先考虑直接暴力枚举四个边界,然后判断是否为有效子矩形

时间复杂度 O( $s^5$ ),产生大量的无效子矩形,妥妥的 TLE。

让我们对以上算法进行优化:

将所有障碍点按横坐标排序并编号为 $1,2,3,…$
从左往右枚举极大子矩形左边界,以整个矩形上下边为边界。
向右扫描,枚举障碍点,修改上下边界使矩阵有效,复杂度 O( $s^2$ )。

枚举左右边界时不要忘了加上整个矩形的左右边界!

特点

复杂度比较优秀,适用于障碍点较少的稀疏图

示题

Vijos 1055 WC2002 奶牛浴场

算法二(悬线法)

时间复杂度 O( $n\times m$ ),空间复杂度 O( $n\times m$ )

重点来了! \拍桌 \拍桌

定义

有效竖线:除了两个端点外,不覆盖任何一个障碍点的竖直线段。
悬线:上端覆盖了一个障碍点或者到达整个矩形上边界的有效竖线。

我们称以点 $(i,j)$ 为底的悬线为点 $(i,j)$ 对应的悬线

思路

一个矩形中共有 $(n-1)\times m$ 条悬线,即除了顶部的点外,其余的各点均有且只有一条与其对应的悬线。

枚举各条悬线,将其向左右两侧尽可能拓展,就可得到一个由 $(n-1)\times m$ 个悬线拓展形成的矩形的集合,而这个集合包含了所有的极大子矩形。

枚举悬线的时间复杂度是 O( $n\times m$ ) 的,即我们要在 O( $1$ ) 内拓展左右区间。

设 height$[ i,j ]$ 为点 $(i,j)$ 对应的悬线的长度,left$[i,j]$ 为点 $(i,j)$ 对应的悬线向左最多拓展到的位置,right$[i,j]$ 为点 $(i,j)$ 对应的悬线向右最多拓展到的位置。

left$[i,j]$ 和 right$[i,j]$先初始化为点 $(i,j)$ 向左右最多拓展到的位置。

这样,若 $(i-1,j)$ 为障碍点,height$[i,j]$=1,left$[i,j]$=0,right$[i,j]$=$m$

若 $(i-1,j)$ 不为障碍点:

height$[i,j]$=height$[i-1,j]+1$
left$[i,j]$=$max$ ( left$[i-1,j]$ , left$[i,j]$ )
right$[i,j]$=$min$ ( right$[i-1,j]$ , right$[i,j]$ )

这样就可以利用递推式,在 O( $1$ ) 的复杂度内拓展左右区间。

特点

复杂度与障碍点数无关,适合障碍点较稠密的矩阵求解,在障碍点较少时,不如算法一。

示题

洛谷 P1169 [ZJOI 2007]棋盘制作

题解将发至下一篇博客


参考资料

最大子矩阵问题&悬线法 学习笔记 Clove_unique

0%