悬线法

Summary

悬线法用于求最大子矩形一类问题，例如在 01 矩阵中找面积最大的全同子矩形。悬线指从某点向上延伸、不越过障碍的一段极长竖线。做法是逐行递推每条悬线当前能向左、向右扩展到的最远列边界及其对应高度：新一行的边界由上一行的边界与本行的障碍取交得到，扫描过程中即可枚举出所有极大子矩形并更新答案，整体时间复杂度 O(nm)。相比枚举上下左右四条边界的暴力，它借助逐行递推把重复计算摊掉。例题为洛谷 P4147。

参考资料

• 悬线法 - OI Wiki

简介

悬线法 用于求最大子矩形一类问题。把每个点向上引一条尽量长的「悬线」，逐行递推每条悬线能向左、向右扩展到的最远边界及其高度，即可在 $O(nm)$ 内枚举出所有极大子矩形。

例题

洛谷 P4147 玉蟾宫

给定 $n\times m$ 的网格，每格为可用或障碍，求全部由可用格组成的最大子矩形的面积。