You need to enable JavaScript to run this app. DSA:求避石最大周长矩形的最优解法,能否达到O(N*M)时间复杂度?
优惠活动
大模型
产品
解决方案
定价
更多

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)线性级别

按照解法逻辑对两个给定示例做校验:

  1. 第一组输入网格中,枚举到r1=0行、r2=2行时,可形成左右边界的候选列是c0、c1、c4,校验后发现c0到c1的区间完全满足四边无石头的要求,对应周长10,和题目给出的加粗边界结果完全匹配
  2. 第二组输入网格中,枚举到r1=1行、r2=4行时,候选列是c0、c1、c2、c5,校验后c0到c5的远区间完全符合边界要求,对应周长20,和题目给出的输出结果完全匹配

内容的提问来源于stack exchange,提问作者Venu Nathan

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.19 14:24:04