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

Question

给定一个 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的二进制矩阵。在这种情况下，返回值将是 Cell 1:(2, 1) 和 Cell 2:(4, 4)。生成的子矩阵可以是正方形或矩形。返回值也可以是全 0 的最大子矩阵的大小，在本例中为 3 × 4。

Answer 1

这是一个基于 "Largest Rectangle in a Histogram" problem 的解决方案@j_random_hacker 在评论中建议:

[Algorithm] works by iterating through rows from top to bottom, for each row solving this problem, where the "bars" in the "histogram" consist of all unbroken upward trails of zeros that start at the current row (a column has height 0 if it has a 1 in the current row).

输入矩阵 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