查找包含在N×N二进制矩阵只有零点最大的矩形

本文介绍了查找包含在N×N二进制矩阵只有零点最大的矩形的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

考虑的N×N二进制矩阵（只有00或11的含），我们如何去寻找包含最大的矩形全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个二进制矩阵。在这种情况下，返回值将是细胞1：（2，1）和小区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：

Here's a solution based on the "Largest Rectangle in a Histogram" problem suggested by @j_random_hacker in the comments:

[算法]的工作原理是通过迭代   行从上到下，对于每一行   解决此问题的，这里的   在柱状图棒由   零的所有不间断的向上路径   启动在当前行（一   列具有高度0，如果它有一个1中   当前行）。

[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).

输入矩阵垫可以是任意可迭代的，例如，文件或网络流。只有一行需要是可用的时间。

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.

最新版本的测试是在 gist.github/776423