二维二进制矩阵中 1 的最大矩形 [英] Largest rectangle of 1's in 2d binary matrix

问题描述

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

There is a problem to find the maximum area of the 1 in the 0-1 matrix. In this problem there are two cases:

1. 要测量的面积为正方形.DP 很简单.

1. area to be measure is of shape square. that's simple one by DP.

要测量的区域为矩形.我无法为此想出最佳解决方案.

area to be measure is of the shape of rectangle. i am not able to think a optimal solution for this.

示例:

010101
101001
111101
110101

最大的矩形面积为 4(第 3 行第 5 列，第 3、4 行还有一个).我们也可以得到所有这些矩形吗?

The largest rectangle has an area of 4 (3rd row , 5th column and one more in 3rd,4th row). Can we also get all those rectangle ?

推荐答案

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

I'll step through a few solutions of increasing difficulty / decreasing runtime complexity.

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

First, a brute force solution. Generate every possible rectangle. You can do this by iterating through every pair of points (r1,c1) (r2,c2) with r1 ≤ r2 and c1 ≤ c2 (can be done with 4 for loops). If a rectangle does not contain a 0, you compare the area to the largest area found so far. This is an O(R^3C^3).

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

We can speed up the valid rectangle check to O(1). We do this by doing a DP where dp(r, c) stores the number of 0's in the rectangle ((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)+(matrix[r][c]?0:1)

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

Then the number of 0's in ((r1, c1), (r2, c2)) is

• 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 检查矩形是否有效.

You can then check if a rectangle is valid by nzeroes(r1,c1,r2,c2) == 0.

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

There is an O(R^2C) solution for this using a simple DP and a stack. The DP works per column, by finding the number of 1 cells above a cell until the next 0. The dp is as follows:

• dp(r, 0) = 0
• dp(r, c) = 0 如果 matrix[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) 中的问题:

It is also possible to solve the problem in O(RC) using three DP’s:

• 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
• h(r, c) = 0 如果 matrix[r][c] == 0

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

• h(0, c) = 0
• h(r, c) = 0 if matrix[r][c] == 0

• h(r, c) = h(r-1, c)+1 otherwise

l(r, 0) = 0

l(r, 0) = 0

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

l(r, c) = min(l(r − 1, c), c − p) otherwise

r(r,C+1) = 0

r(r,C+1) = 0

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

where p is the column of the previous 0 as we populate l from left-right and r from right-left.

答案是:

• 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 个 for 循环来完成).如果矩形不包含 0，则将该区域与迄今为止找到的最大区域进行比较.

This works because of the observation that the largest rectangle will always touch a 0 (considering the edge as being covered in 0's) on all four sides. By considering all rectangles with at least top, left and right touching a 0, we cover all candidate rectangles. Generate every possible rectangle. You can do this by iterating through every pair of points (r1,c1) (r2,c2) with r1 ≤ r2 and c1 ≤ c2 (can be done with 4 for loops). If a rectangle does not contain a 0, you compare the area to the largest area found so far.

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

Note: I adapted the above from an answer I wrote up here - refer to the section "Ben's Mom". In that writeup, the 0's are trees. That writeup also has better formatting.

这篇关于二维二进制矩阵中 1 的最大矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！