Найти самый большой прямоугольник, содержащий только нули в двоичной матрице 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 & times; 6. возвращаемое значение в этом случае будет Ячейка 1: (2, 1) и Ячейка 2: (4, 4). Результирующая подматрица может быть квадратной или прямоугольной. Возвращаемое значение также может быть размером самой большой субматрицы из всех 0, в этом примере 3 раза; 4.

Answer 1

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

Answer 2

Пожалуйста, посмотрите на Увеличьте прямоугольную область под гистограммой , а затем продолжайте читать решение ниже.

Traverse the matrix once and store the following;

For x=1 to N and y=1 to N    
F[x][y] = 1 + F[x][y-1] if A[x][y] is 0 , else 0

Then for each row for x=N to 1 
We have F[x] -> array with heights of the histograms with base at x.
Use O(N) algorithm to find the largest area of rectangle in this histogram = H[x]

From all areas computed, report the largest.

Сложность по времени O (N * N) = O (N²) (для двоичной матрицы NxN)

Пример:

Initial array    F[x][y] array
 0 0 0 0 1 0     1 1 1 1 0 1
 0 0 1 0 0 1     2 2 0 2 1 0
 0 0 0 0 0 0     3 3 1 3 2 1
 1 0 0 0 0 0     0 4 2 4 3 2
 0 0 0 0 0 1     1 5 3 5 4 0
 0 0 1 0 0 0     2 6 0 6 5 1

 For x = N to 1
 H[6] = 2 6 0 6 5 1 -> 10 (5*2)
 H[5] = 1 5 3 5 4 0 -> 12 (3*4)
 H[4] = 0 4 2 4 3 2 -> 10 (2*5)
 H[3] = 3 3 1 3 2 1 -> 6 (3*2)
 H[2] = 2 2 0 2 1 0 -> 4 (2*2)
 H[1] = 1 1 1 1 0 1 -> 4 (1*4)

 The largest area is thus H[5] = 12

Answer 3

Вот решение Python3, которое возвращает позицию в дополнение к области наибольшего прямоугольника:

#!/usr/bin/env python3

import numpy

s = '''0 0 0 0 1 0
0 0 1 0 0 1
0 0 0 0 0 0
1 0 0 0 0 0
0 0 0 0 0 1
0 0 1 0 0 0'''

nrows = 6
ncols = 6
skip = 1
area_max = (0, [])

a = numpy.fromstring(s, dtype=int, sep=' ').reshape(nrows, ncols)
w = numpy.zeros(dtype=int, shape=a.shape)
h = numpy.zeros(dtype=int, shape=a.shape)
for r in range(nrows):
    for c in range(ncols):
        if a[r][c] == skip:
            continue
        if r == 0:
            h[r][c] = 1
        else:
            h[r][c] = h[r-1][c]+1
        if c == 0:
            w[r][c] = 1
        else:
            w[r][c] = w[r][c-1]+1
        minw = w[r][c]
        for dh in range(h[r][c]):
            minw = min(minw, w[r-dh][c])
            area = (dh+1)*minw
            if area > area_max[0]:
                area_max = (area, [(r-dh, c-minw+1, r, c)])

print('area', area_max[0])
for t in area_max[1]:
    print('Cell 1:({}, {}) and Cell 2:({}, {})'.format(*t))

Выход:

area 12
Cell 1:(2, 1) and Cell 2:(4, 4)

Answer 4

Вот метод Дж. Ф. Себастьяна, переведенный на C #:

private Vector2 MaxRectSize(int[] histogram) {
        Vector2 maxSize = Vector2.zero;
        int maxArea = 0;
        Stack<Vector2> stack = new Stack<Vector2>();

        int x = 0;
        for (x = 0; x < histogram.Length; x++) {
            int start = x;
            int height = histogram[x];
            while (true) {
                if (stack.Count == 0 || height > stack.Peek().y) {
                    stack.Push(new Vector2(start, height));

                } else if(height < stack.Peek().y) {
                    int tempArea = (int)(stack.Peek().y * (x - stack.Peek().x));
                    if(tempArea > maxArea) {
                        maxSize = new Vector2(stack.Peek().y, (x - stack.Peek().x));
                        maxArea = tempArea;
                    }

                    Vector2 popped = stack.Pop();
                    start = (int)popped.x;
                    continue;
                }

                break;
            }
        }

        foreach (Vector2 data in stack) {
            int tempArea = (int)(data.y * (x - data.x));
            if(tempArea > maxArea) {
                maxSize = new Vector2(data.y, (x - data.x));
                maxArea = tempArea;
            }
        }

        return maxSize;
    }

    public Vector2 GetMaximumFreeSpace() {
        // STEP 1:
        // build a seed histogram using the first row of grid points
        // example: [true, true, false, true] = [1,1,0,1]
        int[] hist = new int[gridSizeY];
        for (int y = 0; y < gridSizeY; y++) {
            if(!invalidPoints[0, y]) {
                hist[y] = 1;
            }
        }

        // STEP 2:
        // get a starting max area from the seed histogram we created above.
        // using the example from above, this value would be [1, 1], as the only valid area is a single point.
        // another example for [0,0,0,1,0,0] would be [1, 3], because the largest area of contiguous free space is 3.
        // Note that at this step, the heigh fo the found rectangle will always be 1 because we are operating on
        // a single row of data.
        Vector2 maxSize = MaxRectSize(hist);
        int maxArea = (int)(maxSize.x * maxSize.y);

        // STEP 3:
        // build histograms for each additional row, re-testing for new possible max rectangluar areas
        for (int x = 1; x < gridSizeX; x++) {
            // build a new histogram for this row. the values of this row are
            // 0 if the current grid point is occupied; otherwise, it is 1 + the value
            // of the previously found historgram value for the previous position. 
            // What this does is effectly keep track of the height of continous avilable spaces.
            // EXAMPLE:
            //      Given the following grid data (where 1 means occupied, and 0 means free; for clairty):
            //          INPUT:        OUTPUT:
            //      1.) [0,0,1,0]   = [1,1,0,1]
            //      2.) [0,0,1,0]   = [2,2,0,2]
            //      3.) [1,1,0,1]   = [0,0,1,0]
            //
            //  As such, you'll notice position 1,0 (row 1, column 0) is 2, because this is the height of contiguous
            //  free space.
            for (int y = 0; y < gridSizeY; y++) {                
                if(!invalidPoints[x, y]) {
                    hist[y] = 1 + hist[y];
                } else {
                    hist[y] = 0;
                }
            }

            // find the maximum size of the current histogram. If it happens to be larger
            // that the currently recorded max size, then it is the new max size.
            Vector2 maxSizeTemp = MaxRectSize(hist);
            int tempArea = (int)(maxSizeTemp.x * maxSizeTemp.y);
            if (tempArea > maxArea) {
                maxSize = maxSizeTemp;
                maxArea = tempArea;
            }
        }

        // at this point, we know the max size
        return maxSize;            
    }

Несколько замечаний по этому поводу:

1. Эта версия предназначена для использования с Unity API. Вы можете легко сделать это более общим, заменив экземпляры Vector2 на KeyValuePair. Vector2 используется только для удобного способа хранения двух значений.
2. invalidPoints [] является массивом bool, где true означает, что точка сетки «используется», а false означает, что это не так.

Answer 5

Решение с пространственной сложностью O (столбцы) [Может быть изменено также на O (строки)] и временной сложностью O (строки * столбцы)

public int maximalRectangle(char[][] matrix) {
    int m = matrix.length;
    if (m == 0)
        return 0;
    int n = matrix[0].length;
    int maxArea = 0;
    int[] aux = new int[n];
    for (int i = 0; i < n; i++) {
        aux[i] = 0;
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            aux[j] = matrix[i][j] - '0' + aux[j];
            maxArea = Math.max(maxArea, maxAreaHist(aux));
        }
    }
    return maxArea;
}

public int maxAreaHist(int[] heights) {
    int n = heights.length;
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(0);
    int maxRect = heights[0];
    int top = 0;
    int leftSideArea = 0;
    int rightSideArea = heights[0];
    for (int i = 1; i < n; i++) {
        if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) {
            stack.push(i);
        } else {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                top = stack.pop();
                rightSideArea = heights[top] * (i - top);
                leftSideArea = 0;
                if (!stack.isEmpty()) {
                    leftSideArea = heights[top] * (top - stack.peek() - 1);
                } else {
                    leftSideArea = heights[top] * top;
                }
                maxRect = Math.max(maxRect, leftSideArea + rightSideArea);
            }
            stack.push(i);
        }
    }
    while (!stack.isEmpty()) {
        top = stack.pop();
        rightSideArea = heights[top] * (n - top);
        leftSideArea = 0;
        if (!stack.isEmpty()) {
            leftSideArea = heights[top] * (top - stack.peek() - 1);
        } else {
            leftSideArea = heights[top] * top;
        }
        maxRect = Math.max(maxRect, leftSideArea + rightSideArea);
    }
    return maxRect;
}

Но я получаю исключение превышения лимита времени, когда я пытаюсь сделать это на LeetCode. Есть ли менее сложное решение?

Answer 6

Я предлагаю метод O (nxn).

Сначала вы можете перечислить все максимально пустые прямоугольники. Пустой означает, что он охватывает только 0. Максимальный пустой прямоугольник таков, что он не может быть вытянут в направлении, не покрывая (хотя бы) один 1.

Документ с алгоритмом O (nxn) для создания такого списка можно найти по адресу www.ulg.ac.be / telecom / rectangles , а также исходный код (не оптимизирован). Нет необходимости сохранять список, достаточно вызывать функцию обратного вызова каждый раз, когда алгоритм находит прямоугольник, и сохранять только самый большой (или выбрать другой критерий, если хотите).

Обратите внимание, что существует доказательство (см. Статью), что число самых больших пустых прямоугольников ограничено количеством пикселей изображения (в данном случае nxn).

Следовательно, выбор оптимального прямоугольника может быть сделан в O (nxn), и общий метод также O (nxn).

На практике этот метод очень быстрый и используется для анализа видеопотока в реальном времени.

Answer 7

Вот вариант решения jfs, в котором также указывается позиция наибольшего прямоугольника:

from collections import namedtuple
from operator import mul

Info = namedtuple('Info', 'start height')

def max_rect(mat, value=0):
    """returns (height, width, left_column, bottom_row) of the largest rectangle 
    containing all `value`'s.

    Example:
    [[0, 0, 0, 0, 0, 0, 0, 0, 3, 2],
     [0, 4, 0, 2, 4, 0, 0, 1, 0, 0],
     [1, 0, 1, 0, 0, 0, 3, 0, 0, 4],
     [0, 0, 0, 0, 4, 2, 0, 0, 0, 0],
     [0, 0, 0, 2, 0, 0, 0, 0, 0, 0],
     [4, 3, 0, 0, 1, 2, 0, 0, 0, 0],
     [3, 0, 0, 0, 2, 0, 0, 0, 0, 4],
     [0, 0, 0, 1, 0, 3, 2, 4, 3, 2],
     [0, 3, 0, 0, 0, 2, 0, 1, 0, 0]]
     gives: (3, 4, 6, 5)
    """
    it = iter(mat)
    hist = [(el==value) for el in next(it, [])]
    max_rect = max_rectangle_size(hist) + (0,)
    for irow,row in enumerate(it):
        hist = [(1+h) if el == value else 0 for h, el in zip(hist, row)]
        max_rect = max(max_rect, max_rectangle_size(hist) + (irow+1,), key=area)
        # irow+1, because we already used one row for initializing max_rect
    return max_rect

def max_rectangle_size(histogram):
    stack = []
    top = lambda: stack[-1]
    max_size = (0, 0, 0) # height, width and start position 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), 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), start), key=area)

    return max_size

def area(size):
    return size[0] * size[1]