3

所以这个问题本身就很简单，每次输入，给我一个宽度和高度，都不会超过200，然后是一系列的0和1来代表二维平面。

像这样。

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 重新评估。什么是最佳算法？

4

4 回答 4

2

类似于以下问题：找到总和最大的子矩阵。这可以通过 O(n^3) 算法来完成。我相信你可以在 stackoverflow 上找到它或在互联网上搜索。

对于这个问题，你可以用 -INF 替换 0，然后应用上述算法找到最大的矩形区域。

于 2013-01-25T15:19:02.260 回答
1

有几条评论指向线性复杂度的答案，但我想我会提到似乎是一个简单的 O(n^2) 算法。

对于每个单元格，计算完全位于其下方和完全位于其左侧的单元格的数量。您可以通过从左下角开始按行排列，查看其下方的单元格并查看其左侧单元格的小计，从而在线性时间内完成此操作。

一个矩形可以由其左下角的点和右上角的点来定义。当然，它有四个角。如果您将先前计算的左下角和右上角的总数相加，并减去左上角和右下角的总数，您将得到矩形中的单元格数量 - 矩形之外的单元格要么根本不计算，要么被取消。该矩形的确切位置取决于您在极端情况下所做的事情以及您如何解释“完全在其下方并完全在其左侧”。但是，给定定义一个矩形的两个角，您可以通过检索四个数字并进行加法和减法来计算其中的总和。

对于由两个点定义的矩形，需要考虑 O(n^2) 个矩形（因为我将 n 视为数据的大小，这意味着要搜索的区域有 O(n) 个点）。由于我可以在恒定时间内计算每个矩形内的总和并丢弃那些没有总和的那些，这意味着所有点都被覆盖，所以总成本是 O(n^2)。

于 2013-01-25T19:52:13.197 回答
1

我能想到的最好的算法是遍历 2D 矩阵并从左上角的一个角开始，在这种情况下，从右下角的一个角开始，执行以下操作：

对于你找到的每一个 1，找到最长的水平字符串 1 以及垂直字符串。为了效率，右边的位置比左边的位置少一个（你仍然需要得到它的垂直最大值）；您只需在每次达到 0 时重新开始计数。当您进入下一行时同样适用。

这两个数字的乘积是从该位置开始的矩形的最大可能面积。在另一个数据结构中，存储位置、maxWidth 和 maxHeight，并根据顶部区域最大的区域进行排序。避免放置子矩形以提高效率；您可以通过忽略 maxHeight 小于或等于其自身值的右相邻 1 来做到这一点。我把数据结构的选择留给你。

现在您浏览您创建的数据结构并从最大矩形开始。找到最接近的 0。您将矩形分成 2 个子矩形，排除 0 所在的水平线和 2 个排除 0 所在的垂直线的子矩形。如果 0 在边缘，您将只得到 3 个子矩形如果它在一个角落，只有 2。删除矩形，插入新创建的子矩形并保持最大区域顺序。现在对数据结构中的下一个矩形重复此过程，直到找到一个没有 0 的矩形。那是最大的一个。

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

于 2013-01-25T17:37:03.413 回答
0 
 /*

Given a 2D binary array(2D array of 0's and 1's) with m rows and n columns,find area of largest sub-array(rectangle) 
consisting entirely of 1's.
*/

public int findMaxRectangleArea(int[][] A,int m,int n){
        // m=rows & n=cols according to question

        int[] single;
        int largeX = 0,largest = 0; 
        for (int i = 0; i < m; i++) {
              single = new int[n];            //one d array used to check line by line & it's size will be n
              for (int k = i; k < m; k++) {                // this is used for to run until i contains element
                        int a = 0;
                    int y = k - i + 1;  // is used for row and col of the comming array
                    int shrt = 0,ii = 0,small = 0; 
                                    int mix = 0;
                    int findX = 0; 
                   for (int j = 0; j < n; j++) {
                       single[j] = single[j] + A[k][j]; // postions element are added
                      if (single[j] == y) {           //element position equals
                            shrt = (a == 0) ? j : shrt;       //shortcut
                            a=a+1;
                        if (a > findX) {
                            findX = a;
                            mix = shrt;
                        }
                    } else {
                        a = 0;
                    }
                }
                   a = findX;
                   a = (a == y) ? a - 1 : a;
                         if (a * y > largeX * largest) {  // here i am checking the values with xy
                           largeX = a;
                           largest = y;
                           ii = i;
                           small = mix;
                           }
            }
        }// end of  loop

return largeX*largest;
    }       //end of method




/*
     Time complexity = method contains 2 inner loops so m*m & 1 outer loop n

     so the complexity is------------------->  O((m^2)*n)

     Space Complexity is-------it's directly proportional to the size of the array i.e ---------------> (m*m)+n

*/
于 2013-02-27T04:44:00.080 回答