二维二进制矩阵中1的最大矩形

Question

在0-1矩阵中找到1的最大面积是一个问题。在此问题中，有两种情况：

1. 要测量的区域是正方形。这很简单，DP。

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

例：

010101
101001
111101
110101

最大的矩形的面积为4（第3行，第5列，第3、4行另外一个）。我们还能得到所有这些矩形吗？

Answer 1

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

首先，解决暴力问题。生成每个可能的矩形。您可以通过迭代r1≤r2和c1≤c2的每对点（r1，c1）（r2，c2）来完成此操作（可以使用4个for循环来完成）。如果矩形不包含0，则将面积与迄今为止找到的最大面积进行比较。这是O（R
^ 3C ^ 3）。

我们可以将有效的矩形检查加快到O（1）。我们通过执行DP来做到这一点，其中dp（r，c）在矩形（（1，1），（r，c））中存储0的数目。

• 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）解决方案。DP通过找到一个单元格上方的1个单元格的数量直到下一个0来对每列工作。dp如下：

• dp（r，0）= 0
• 如果matrix [r] [c] == 0，则dp（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之前我们找到多少个单元格？
• l（r，c）：我们可以在（r，c）和高度h（r，c）处扩展一个具有右下角的矩形吗？
• r（r，c）：我们可以在（r，c）和高度h（r，c）的左下角延伸一个矩形到多远？

三种重复关系是：

• h（0，c）= 0
• 如果matrix [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≤r2和c1≤c2的每对点（r1，c1）（r2，c2）来完成此操作（可以使用4个for循环来完成）。如果矩形不包含0，则将面积与迄今为止找到的最大面积进行比较。

注意：我是根据我在这里写下的答案改编以上内容的-
请参阅“ Ben的妈妈”部分。在该文章中，0为树。该文章也具有更好的格式。