algorithm - 找到N×N二进制矩阵中仅包含零的最大矩形




arrays (4)

给定NxN二进制矩阵(仅包含0或1),我们如何才能找到包含全0的最大矩形?

例:

      I
    0 0 0 0 1 0
    0 0 1 0 0 1
II->0 0 0 0 0 0
    1 0 0 0 0 0
    0 0 0 0 0 1 <--IV
    0 0 1 0 0 0
            IV 

对于上面的例子,它是一个6×6的二进制矩阵。 在这种情况下,返回值将是单元格1:(2,1)和单元格2:(4,4)。 得到的子矩阵可以是正方形或矩形。 返回值也可以是所有0的最大子矩阵的大小,在该示例中为3×4。


我提出了一种O(nxn)方法。

首先,您可以列出所有最大的空矩形。 空意味着它仅覆盖0。 最大的空矩形使得它不能在不覆盖(至少)1的方向上延伸。

可以在www.ulg.ac.be/telecom/rectangles以及源代码(未优化)中找到提供O(nxn)算法以创建此类列表的www.ulg.ac.be/telecom/rectangles 。 不需要存储列表,每次算法找到矩形时调用回调函数就足够了,并且只存储最大的一个(或者如果需要,可以选择另一个标准)。

注意,存在证据(参见论文),最大空矩形的数量受图像的像素数(在这种情况下为n×n)的限制。

因此,选择最佳矩形可以在O(nxn)中完成,整个方法也是O(nxn)。

实际上,这种方法非常快,并且用于实时视频流分析。


空间复杂度为O(列)的解决方案[也可以修改为O(行)]和时间复杂度O(行*列)

public int maximalRectangle(char[][] matrix) {
    int m = matrix.length;
    if (m == 0)
        return 0;
    int n = matrix[0].length;
    int maxArea = 0;
    int[] aux = new int[n];
    for (int i = 0; i < n; i++) {
        aux[i] = 0;
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            aux[j] = matrix[i][j] - '0' + aux[j];
            maxArea = Math.max(maxArea, maxAreaHist(aux));
        }
    }
    return maxArea;
}

public int maxAreaHist(int[] heights) {
    int n = heights.length;
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(0);
    int maxRect = heights[0];
    int top = 0;
    int leftSideArea = 0;
    int rightSideArea = heights[0];
    for (int i = 1; i < n; i++) {
        if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) {
            stack.push(i);
        } else {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                top = stack.pop();
                rightSideArea = heights[top] * (i - top);
                leftSideArea = 0;
                if (!stack.isEmpty()) {
                    leftSideArea = heights[top] * (top - stack.peek() - 1);
                } else {
                    leftSideArea = heights[top] * top;
                }
                maxRect = Math.max(maxRect, leftSideArea + rightSideArea);
            }
            stack.push(i);
        }
    }
    while (!stack.isEmpty()) {
        top = stack.pop();
        rightSideArea = heights[top] * (n - top);
        leftSideArea = 0;
        if (!stack.isEmpty()) {
            leftSideArea = heights[top] * (top - stack.peek() - 1);
        } else {
            leftSideArea = heights[top] * top;
        }
        maxRect = Math.max(maxRect, leftSideArea + rightSideArea);
    }
    return maxRect;
}

但是当我在LeetCode上尝试这个时,我得到Time Limite超过了excpetion。 有没有那么复杂的解决方案?


这是一个Python3解决方案,除了最大矩形的区域外还返回位置:

#!/usr/bin/env python3

import numpy

s = '''0 0 0 0 1 0
0 0 1 0 0 1
0 0 0 0 0 0
1 0 0 0 0 0
0 0 0 0 0 1
0 0 1 0 0 0'''

nrows = 6
ncols = 6
skip = 1
area_max = (0, [])

a = numpy.fromstring(s, dtype=int, sep=' ').reshape(nrows, ncols)
w = numpy.zeros(dtype=int, shape=a.shape)
h = numpy.zeros(dtype=int, shape=a.shape)
for r in range(nrows):
    for c in range(ncols):
        if a[r][c] == skip:
            continue
        if r == 0:
            h[r][c] = 1
        else:
            h[r][c] = h[r-1][c]+1
        if c == 0:
            w[r][c] = 1
        else:
            w[r][c] = w[r][c-1]+1
        minw = w[r][c]
        for dh in range(h[r][c]):
            minw = min(minw, w[r-dh][c])
            area = (dh+1)*minw
            if area > area_max[0]:
                area_max = (area, [(r-dh, c-minw+1, r, c)])

print('area', area_max[0])
for t in area_max[1]:
    print('Cell 1:({}, {}) and Cell 2:({}, {})'.format(*t))

输出:

area 12
Cell 1:(2, 1) and Cell 2:(4, 4)

这是基于@j_random_hacker在评论中提出的“直方图中最大矩形”问题的解决方案:

[算法]通过从上到下迭代行来工作,每行解决这个问题 ,其中“直方图”中的“条形”由从当前行开始的所有零的不间断向上轨迹组成(列具有高度0如果它在当前行中有1)。

输入矩阵mat可以是任意可迭代的,例如文件或网络流。 一次只需要一行。

#!/usr/bin/env python
from collections import namedtuple
from operator import mul

Info = namedtuple('Info', 'start height')

def max_size(mat, value=0):
    """Find height, width of the largest rectangle containing all `value`'s."""
    it = iter(mat)
    hist = [(el==value) for el in next(it, [])]
    max_size = max_rectangle_size(hist)
    for row in it:
        hist = [(1+h) if el == value else 0 for h, el in zip(hist, row)]
        max_size = max(max_size, max_rectangle_size(hist), key=area)
    return max_size

def max_rectangle_size(histogram):
    """Find height, width of the largest rectangle that fits entirely under
    the histogram.
    """
    stack = []
    top = lambda: stack[-1]
    max_size = (0, 0) # height, width of the largest rectangle
    pos = 0 # current position in the histogram
    for pos, height in enumerate(histogram):
        start = pos # position where rectangle starts
        while True:
            if not stack or height > top().height:
                stack.append(Info(start, height)) # push
            elif stack and height < top().height:
                max_size = max(max_size, (top().height, (pos - top().start)),
                               key=area)
                start, _ = stack.pop()
                continue
            break # height == top().height goes here

    pos += 1
    for start, height in stack:
        max_size = max(max_size, (height, (pos - start)), key=area)    
    return max_size

def area(size):
    return reduce(mul, size)

解是O(N) ,其中N是矩阵中元素的数量。 它需要额外的O(ncols)内存,其中ncols是矩阵中的列数。

测试的最新版本位于https://gist.github.com/776423







arrays