极大化思想

极大化思想适用于解决最大子矩形问题

即:在一个给定的矩形中有一些障碍点,对于这些障碍点,我们需要找一个最大的子矩形,子矩形需要保证在这个轮廓内不包含任何障碍点,以及轮廓上是可以有点的,但是这个轮廓是与整个矩形平行或者是重合.

有效子矩形:内部不含任何障碍点的,同时边界与坐标轴是平行的子矩形

极大子矩形:每条边都不能向外拓展的有效子矩形

最大子矩形:所有有效子矩形中最大的一个或者多个

极大化思想:在一个有障碍点的矩形钟的最大子矩形一个是一个极大子矩形

\[Max_{rectangle}=max(max(effective_{rectangle},maximun_{rectangle}),Max_{rectangle})\]

思路:

通过枚举所有的极大子矩形,找出最大子矩形.

根据障碍点数和矩形面积不同,分出两种算法,算法一为障碍点数少的情况,算法二为矩形面积小的情况.


算法一:

时间复杂度:

\[O(s^2)\]

空间复杂度:

\[O(NM)\]

思路:

从极大子矩形的性质入手.

极大子矩形的性质:一个极大组举行的每一条边一定都不能向外扩展.更进一步地说,一个有效子矩形是极大子矩形的条件是这个子矩形的每条边要么覆盖了障碍点,要么与整个矩形的边界重合.

基本思路:枚举

枚举上下左右四个边界,然后判断组成的这个矩形是不是有效子矩形.

时间复杂度

\[O(S^5)\]

改进的地方:因为枚举了所有的矩形,所以一定会有大量的无效子矩形.

进阶:

枚举左右边界,对处在边界内的点排序.每两个相邻的点和左右边界一起组成一个矩形.

时间复杂度

\[O(S^3)\]

改进的地方:枚举了部分不是极大子矩形的地方

设计算法方向:

1、保证每一个枚举的子矩形都是有效的.

2、保证每一个枚举的子矩形都是极大的.

过程:

枚举极大子矩形的左边界,根据这个左边界,找相关的极大子矩形.

算法优缺点:

优点:利用了极大化思想,编程实现简单.

缺点:不适用与障碍点较密集的情况.


算法二:

思路:

因为算法1优使用的局限性,所以需要考虑当点分布十分密集的情况.所以依赖于整个矩形的面积设计一种算法.

悬线:

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

悬线:上端点覆盖了一个障碍点或达到整个矩形上端的有效竖线

每个悬线都与他底部的点一一对应.

矩形中的每一个点(除了矩形顶部的点)都对应了一个悬线.

悬线个数:(N-1)*M

如果把一个极大子矩形按X周不同切割成多个悬线,则其中至少存在一个合法悬线.并且将这一条悬线通过尽可能地左右移动就可以得到一个子矩形,虽然不是极大子矩形,但是这样来说就只能往下扩展.

定理:

如果将一个悬线向左右两个方向尽可能移动所得到的有效子矩形成为这个悬线所对应的子矩形,那么所有悬线所对应的有效子矩形的集合一定包含了所有极大子矩形的集合

这里的尽可能就是把这个左右两条框一直移到障碍点或者是边界处位置.

最终思路:

那么算法就可以出来了,通过枚举所有的悬线,就可以枚举出所有的极大子矩形.由于每个选项县都与它底部的那个店一一对应,所以悬线的个数=(N-1)*M

在时间复杂度在 O(NM)内完成这个题就需要醉倒对每个悬线的操作时间为 O(1).

我们知道,每一个极大子矩形都可以通过一个悬线左右评议得到.所以对于每一个确定了的悬线,一定要知道他的顶部位置,左右最多移动到的位置.

对于底部为(i,j)的悬线,设他的高为 H[i][j],左右最多移动位置 L[i][j], R[i][j].递推出枚举的每一个悬线的H、L、R即可.

以点(i,j)为底部的悬线.

如果点(i-1,j)为障碍点,那么显然以(i,j)为底的悬线高度为1,而且左右均可以移动到整个矩形的左右边界.

信息 数值
H[i][j] 1
L[i][j] 0
R[i][j] m

如果这个不是障碍点,那么以(i,j)为底的悬线就等于以(i-1,j)为底的悬线 + 点(i-1,j)的线段.

故:

H[i][j] = H[i-1][j] + 1;

L[i][j] = max(L[i-1][j],(i-1,j)左边第一个障碍点的位置).

R的求法类似

综上所述:

H[i][j] = H[i-1][j] +1;

L[i][j] = max(L[i-1][j],(i-1,j)左边第一个障碍点位置)

R[i][j] = min(R[i-1][j],(i-1,j)右边第一个障碍点位置)

面积 S 为(R[i][j] – L[i][j])* H[i][j]

所以这个问题最后的解就是

ret = (R[i][j] – L[i][j])* H[i][j] (1<=i<n,1<=j<=m)

那么这个时间复杂度和空间复杂度都是O(NM)的.

算法对比:

首先时间复杂度不一样,那么就会适用于不同的情况,从时间来考虑,第一种算法对障碍点洗漱的情况比较有效,第二种算法则与障碍点个数没有多少关系,当然有离散化的操作,不过加上离散化,不如第一种算法.

QwQ


推广一: 最大权值子矩形问题

模型:在一个带正权矩形中有一些障碍点,找出一个不包含障碍点的最大权值子矩形.

分析:在一个正权值的矩形中的最大权值子矩形一定是极大子矩形.所以,问题实际上可以依据极大化的思想,利用前面的方法解决.

推广二:最大子正方形问题

模型:在一个矩形钟存在S个障碍点,要求找出最大的不包含障碍点的正方形.

分析:在一个有障碍点的矩形钟的最大有效自证发行一定是一个极大有效子正方形.

注意:每一个极大子矩形对应的极大子正方形可能有多个,但是大小都一样

一些奇怪的东西:

类型一:矩形中的点都是两条垂直线段的交点,有效子矩形可以在边界包含障碍点.

类型二:矩形中的点是单位方格,有效子矩形不能包含任何障碍点.

处理方法与类型一基本相同


By:Wahacer

资料来源:

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

特别鸣谢:王知昆

发表评论

电子邮件地址不会被公开。 必填项已用*标注