Прибл. расположение пустой области в изображении [дубликат]

Вот решение, основанное на проблеме «Самый большой прямоугольник в гистограмме» , предложенной @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