2d二进制矩阵中最大的1的矩形

Question

在0-1矩阵中找到1的最大面积存在问题.在这个问题中有两种情况:

1. 要测量的区域是方形的.DP很简单.

2. 要测量的区域是矩形的形状.我无法为此考虑最佳解决方案.

例:

010101
101001
111101
110101

最大的矩形的面积为4(第3行,第5列,第3行,第4行).我们还可以获得所有这些矩形吗？

Answer 1

我将逐步介绍一些增加难度/降低运行时复杂性的解决方案.

首先是蛮力解决方案.生成每个可能的矩形.你可以通过迭代每对点(r1,c1)(r2,c2)来实现这一点,其中r1≤r2和c1≤c2(可以用4个for循环完成).如果矩形不包含0,则将该区域与到目前为止找到的最大区域进行比较.这是O(R ^ 3C ^ 3).

我们可以将有效的矩形检查加速到O(1).我们通过做DP来实现这一点,其中dp(r,c)存储矩形中的0的数量((1,1),(r,c)).

• dp(r,0)= 0
• dp(0,c)= 0
• dp(r,c)= dp(r-1,c)+ dp(r,c-1)-dp(r-1,c-1)+(矩阵[r] [c]≤0:1)

那么((r1,c1),(r2,c2))中的0的数量是

• nzeroes(r1,c1,r2,c2)= dp [r2] [c2] -dp [r1 -1] [c2] -dp [r2] [c1 -1] + dp [r1 -1] [c1 -1]

然后,您可以通过nzeroes(r1,c1,r2,c2)== 0检查矩形是否有效.

使用简单的DP和堆栈,有一个O(R ^ 2C)解决方案.通过查找单元格上方1个单元格的数量直到下一个0,DP每列工作.dp如下:

dp(r,0)= 0 dp(r,c)= 0如果矩阵[r] [c] == 0 dp(r,c)= dp(r-1,c)+ 1否则

然后,您执行以下操作:

area = 0
for each row r:
  stack = {}
  stack.push((height=0, column=0))
  for each column c:
    height = dp(r, c)
    c1 = c
    while stack.top.height > height:
      c1 = stack.top.column
      stack.pop()
    if stack.top.height != height:
      stack.push((height=height, column=c1))
    for item in stack:
      a = (c - item.column + 1) * item.height
      area = max(area, a)

使用三个DP可以解决O(RC)中的问题:

• h(r,c):如果我们从(r,c)开始向上,我们在第一个0之前找到多少个1个单元？
• l(r,c):我们可以在(r,c)和高度h(r,c)的右下角延伸一个矩形的距离多远？
• r(r,c):我们可以在(r,c)和高度h(r,c)的左下角延伸一个矩形多远？

三个复发关系是:

• h(0,c)= 0
• 如果矩阵[r] [c] == 0,则h(r,c)= 0

• h(r,c)= h(r-1,c)否则为+1

• l(r,0)= 0

• 如果矩阵[r-1] [c] == 0,则l(r,c)= cp

• l(r,c)= min(l(r - 1,c),c - p)否则

• r(r,C + 1)= 0

• 如果矩阵[r-1] [c] == 0,则r(r,c)= pc
• r(r,c)= min(r(r - 1,c),p - c)否则

其中p是前一个0的列,因为我们从左到右填充l,从左到右填充r.

答案是:

• max_r,c(h(r,c)*(l(r,c)+ r(r,c) - 1))

这是有效的,因为观察到最大的矩形将始终在所有四个边上触摸0(考虑边缘被0覆盖).通过考虑至少顶部,左侧和右侧接触0的所有矩形,我们覆盖所有候选矩形.生成每个可能的矩形.您可以通过每对点(R1,C1)(R2,C2)与R1≤R2和C1≤C2(可以用4做了循环)迭代做到这一点.如果矩形不包含0,则将该区域与到目前为止找到的最大区域进行比较.

注意:我根据我在这里写的答案改编了上述内容- 请参阅"Ben's Mom"部分.在那篇文章中,0是树.该写入也有更好的格式.