1在2D二元矩阵最大的矩形 [英] Largest rectangle of 1's in 2d binary matrix

问题描述

有一个问题找到的1中的0-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做了循环）迭代做到这一点。如果一个矩形不包含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）存储在矩形的0的数目（（1，1），（R，C））。

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）+（矩阵[R] [C] 0？ 1）

0在接着的数目（（R1，C1），（R2，C2））是

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.

有一个O（R ^ 2C）解决方案，这一点使用一个简单的DP和堆栈。将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，如果矩阵[R] [C] == 0 DP（R，C）= DP（R-1，C）+ 1，否则

dp(r, 0) = 0 dp(r, c) = 0 if matrix[r][c] == 0 dp(r, c) = dp(r-1, c) + 1 otherwise

您然后执行以下操作：

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)

另外，也可以解决使用为O的问题（RC）3的DP的：

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

• 在H（R，C）：如果我们开始在（R，C）和去向上，有多少1细胞才能找到第一个0
前
• L（R，C）：如何最左边我们可以扩展与右下角的矩形在（R，C）和高度h（R，C）
• R（R，C）：如何最右边才能扩展与左下角的矩形在（R，C）和高度h（R，C）

这三个递推关系是：

• H（0，C）= 0
• 在H（R，C）= 0，如果矩阵[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是previous 0列，因为我们填充升从左右左，右和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）*（1（R，C）+ R（R，C） - 1））

这工作，因为观察到的最大的矩形将永远触摸0（考虑到边缘为被包括在0）四面。通过考虑所有的矩形与至少顶，左，右触摸0，我们涵盖所有候选矩形。生成每一个可能的矩形。你可以通过每对点（R1，C1）（R2，C2）与R1≤R2和C1≤C2（可以用4做了循环）迭代做到这一点。如果一个矩形不包含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.

注：我适应了从上面的回答我写了这里 - 参考参见奔的妈妈。在该书面记录，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在2D二元矩阵最大的矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！