算法找到最大的矩形区域在给定的布尔数组 [英] Algorithm to find the biggest rectangle area in a given boolean array

问题描述

因此​​，问题本身是相当简单的，每个输入，我给定的宽度和高度，既不会超过200，然后一系列0和1重新present 2D平面

喜欢这一点。

  4 5
0 0 1 1 1
0 1 1 1 1
1 1 1 1 1
1 1 1 1 1
 

的目标是找到的区域在合适的，具有12不用的区域来说，矩形只能由1秒

我在想洪水填充在写这一点，但它必须重新评估对阵列中的每个1秒。什么是最佳的算法呢？

解决方案

的最佳算法我能想到的是遍历2D矩阵和从一个角，左上开始，到对向之一，右下在这种情况下，做到以下几点：

有关每1你发现，发现1秒的最长横纹以及垂直之一。为了提高效率，姿势要正确少了一个1比一个它左边（你仍然必须得到它的纵向最大）;您只需重新启动的次数，每次你打一个0同样，当你到下一行。

两个数字的乘积是最大可能的区域为从该位置开始的矩形。在另一数据结构，存储位置，了maxWidth，和了maxHeight并根据在顶部面积最大面积的顺序。避免将subrectangles的效率;可以通过忽略右相邻1用了maxHeight小于或等于其自身的值执行此操作。我离开这个数据结构了的选择给你。

现在你去通过你所创建的数据结构，并开始与最大的矩形。找到最近的0您拆分成矩形2 subrectangles的排除水平线，其中0为2 subrectangles的排除垂直线，其中0。如果在0上的优势，将只得到3 subrectangles如果它是在一个角落里，只2.拆下矩形，将新创建的subrectangles，保持面积最大订单。现在，从数据结构中的下一个矩形，重复这个过程，直到找到不带0的矩形。这是最大的一个。

这应该比检查每一个可能的子矩阵更加高效。

So the question itself is quite simple, each input, I am given a width and height, both won't exceed 200, and then a series of 0 and 1s to represent the 2D plane.

Like this.

4 5
0 0 1 1 1
0 1 1 1 1
1 1 1 1 1
1 1 1 1 1

The goal is to find the area at the right, with an area of 12. Needless to say, rectangles can only be consisted of 1s.

I was thinking about flood-fill while writing this, but it would have to reevaluate for each 1s in the array. What's the optimal algorithm for this?

解决方案

The best algorithm I can think of is to traverse the 2D matrix and starting from one corner, top left, to the facing one, bottom right in this case, do the following:

For every 1 you find, find the longest horizontal string of 1s as well as the vertical one. For efficiency, the position to the right has one less 1 than the one to its left (you still have to get its vertical maximum); you just restart the count every time you hit a 0. Same applies when you get to the next line.

The product of the two numbers is the maximum possible area for the rectangle starting at that position. In another data structure, store the position, maxWidth, and maxHeight and make the order based on area with largest area on top. Avoid placing subrectangles for efficiency; you can do this by ignoring a right-adjacent 1 with a maxHeight less than or equal to its own value. I leave the choice of the data structure up to you.

Now you go through the data structure you created and start with the max rectangle. find the nearest 0. You split the rectangle into 2 subrectangles that exclude the horizontal line where the 0 is in and 2 subrectangles that exclude the vertical line where the 0 is in. If the 0 is on the edge, you will get only 3 subrectangles and if it's in a corner, only 2. Remove the rectangle, insert the newly created subrectangles and maintain the largest area order. Now repeat this process with the next rectangle from the data structure until you find a rectangle with no 0s. That's the biggest one.

This should be more efficient than checking every possible submatrix.

这篇关于算法找到最大的矩形区域在给定的布尔数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！