DSA:求避石最大周长矩形的最优解法,能否达到O(N*M)时间复杂度?
问题规则澄清
首先明确题目的判定边界,避免歧义:
- 仅考虑边与网格线平行的轴对齐矩形,合法矩形的四条边界单元格必须全部为'0'(无石头),矩形内部的单元格没有任何约束
- 矩形周长按照常规方式计算:
2*(横向覆盖列数 + 纵向覆盖行数)
可落地的最快解法逻辑
目前工程上可实现的效率最高的解法,核心思路是通过维度优化减少枚举量,整体步骤如下:
- 先对比网格的行、列数量,选择行数更小的方向作为枚举方向:如果原网格N行M列,N<=M就直接枚举行对;M<N就先把网格转置再枚举行对,最大化减少重复枚举的次数
- 固定上边界行r1,逐行向下移动下边界行r2,过程中维护临时数组
h[c]:记录从r1行到当前r2行,第c列连续为'0'的长度;如果当前遍历的r2行第c列是'1',就把h[c]重置为0,否则h[c]自增1 - 对每个r2行,所有满足
h[c] >= (r2 - r1 +1)的列,都能保证“从r1到r2列c全为'0'”,可作为矩形左右边界的候选列 - 从候选列中找跨度最大的合法列对(c1, c2),校验r1行、r2行从c1到c2的区间是否全为'0',符合条件就计算当前矩形的周长,记录全局最大值
复杂度说明
上述解法的总时间复杂度为 O( min(N,M)^2 * max(N,M) ):
- 枚举所有行对的总次数为k*(k+1)/2,k为两个网格维度中更小的那个值
- 每个行对对应的列遍历操作,时间和更大的网格维度长度成正比
在实际运行中,因为我们自动选择了枚举量更小的方向,这套解法在绝大多数网格规模下的运行效率都是最优的。
关于O(N*M)线性解法的说明
目前不存在能覆盖所有场景的通用线性时间解法:
- 该问题的核心约束需要同时校验四条边界的无石头属性,和最大实心矩形场景下的单调栈一维维护逻辑完全不兼容,无法通过单次线性扫描提取所有合法矩形的最大周长
- 碰到全0网格、石头分布极稀疏的场景,上述优化解法的实际运行速度会非常接近线性,但从最坏情况的复杂度推导,始终达不到严格的O(N*M)线性级别
按照解法逻辑对两个给定示例做校验:
- 第一组输入网格中,枚举到r1=0行、r2=2行时,可形成左右边界的候选列是c0、c1、c4,校验后发现c0到c1的区间完全满足四边无石头的要求,对应周长10,和题目给出的加粗边界结果完全匹配
- 第二组输入网格中,枚举到r1=1行、r2=4行时,候选列是c0、c1、c2、c5,校验后c0到c5的远区间完全符合边界要求,对应周长20,和题目给出的输出结果完全匹配
内容的提问来源于stack exchange,提问作者Venu Nathan
相关产品推荐
相关产品推荐

