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

[算法]通过迭代从上到下的行来工作，对于解决该问题的每一行，其中“直方图”中的“条”由从当前行开始的所有零连续向上的零尾组成（一列的高度为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是矩阵中的列数。