在 N×N 二进制矩阵中查找仅包含零的最大矩形 [英] Find largest rectangle containing only zeros in an N×N binary matrix

问题描述

给定一个 NxN 二进制矩阵(仅包含 0 或 1)，我们如何找到包含所有 0 的最大矩形?

Given an NxN binary matrix (containing only 0's or 1's), how can we go about finding largest rectangle containing all 0's?

示例:

      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.

For the above example, it is a 6×6 binary matrix. the return value in this case will be Cell 1:(2, 1) and Cell 2:(4, 4). The resulting sub-matrix can be square or rectangular. The return value can also be the size of the largest sub-matrix of all 0's, in this example 3 × 4.

推荐答案

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

[算法] 通过迭代来工作行从上到下，每行解决这个问题，其中直方图"中的条"由所有不间断的向上的零轨迹从当前行开始(a如果列有 1 英寸，则其高度为 0当前行).

[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 可以是任意的可迭代对象，例如文件或网络流.一次只需要一行可用.

The input matrix mat may be an arbitrary iterable e.g., a file or a network stream. Only one row is required to be available at a time.

#!/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 是矩阵中的列数.

The solution is O(N), where N is the number of elements in a matrix. It requires O(ncols) additional memory, where ncols is the number of columns in a matrix.

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

Latest version with tests is at https://gist.github.com/776423

这篇关于在 N×N 二进制矩阵中查找仅包含零的最大矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！