Найти наибольший прямоугольник, содержащий только нули в двоичной матрице N × N

Ответ 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

Ответ 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

Ответ 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)

Ответ 4

Вот метод J.F. Sebastians, переведенный на С#:

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;            
    }

Несколько замечаний об этом:

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

Ответ 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;
}

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

Ответ 6

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

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

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

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

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

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

Ответ 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]

Ответ 8

Чтобы быть полным, здесь версия С#, которая выводит координаты прямоangularьника. Это основано на ответе dmarra, но без каких-либо других зависимостей. Есть только функция bool GetPixel (int x, int y), которая возвращает true, когда пиксель установлен в координатах x, y.

    public struct INTRECT
    {
        public int Left, Right, Top, Bottom;

        public INTRECT(int aLeft, int aTop, int aRight, int aBottom)
        {
            Left = aLeft;
            Top = aTop;
            Right = aRight;
            Bottom = aBottom;
        }

        public int Width { get { return (Right - Left + 1); } }

        public int Height { get { return (Bottom - Top + 1); } }

        public bool IsEmpty { get { return Left == 0 && Right == 0 && Top == 0 && Bottom == 0; } }

        public static bool operator ==(INTRECT lhs, INTRECT rhs)
        {
            return lhs.Left == rhs.Left && lhs.Top == rhs.Top && lhs.Right == rhs.Right && lhs.Bottom == rhs.Bottom;
        }

        public static bool operator !=(INTRECT lhs, INTRECT rhs)
        {
            return !(lhs == rhs);
        }

        public override bool Equals(Object obj)
        {
            return obj is INTRECT && this == (INTRECT)obj;
        }

        public bool Equals(INTRECT obj)
        {
            return this == obj;
        }

        public override int GetHashCode()
        {
            return Left.GetHashCode() ^ Right.GetHashCode() ^ Top.GetHashCode() ^ Bottom.GetHashCode();
        }
    }

    public INTRECT GetMaximumFreeRectangle()
    {
        int XEnd = 0;
        int YStart = 0;
        int MaxRectTop = 0;
        INTRECT MaxRect = new INTRECT();
        // 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[Height];
        for (int y = 0; y < Height; y++)
        {
            if (!GetPixel(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.
        Tuple<int, int> maxSize = MaxRectSize(hist, out YStart);
        int maxArea = (int)(maxSize.Item1 * maxSize.Item2);
        MaxRectTop = YStart;
        // STEP 3:
        // build histograms for each additional row, re-testing for new possible max rectangluar areas
        for (int x = 1; x < Width; 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 < Height; y++)
            {
                if (!GetPixel(x, y))
                {
                    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.
            Tuple<int, int> maxSizeTemp = MaxRectSize(hist, out YStart);
            int tempArea = (int)(maxSizeTemp.Item1 * maxSizeTemp.Item2);
            if (tempArea > maxArea)
            {
                maxSize = maxSizeTemp;
                maxArea = tempArea;
                MaxRectTop = YStart;
                XEnd = x;
            }
        }
        MaxRect.Left = XEnd - maxSize.Item1 + 1;
        MaxRect.Top = MaxRectTop;
        MaxRect.Right = XEnd;
        MaxRect.Bottom = MaxRectTop + maxSize.Item2 - 1;

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

    private Tuple<int, int> MaxRectSize(int[] histogram, out int YStart)
    {
        Tuple<int, int> maxSize = new Tuple<int, int>(0, 0);
        int maxArea = 0;
        Stack<Tuple<int, int>> stack = new Stack<Tuple<int, int>>();
        int x = 0;
        YStart = 0;
        for (x = 0; x < histogram.Length; x++)
        {
            int start = x;
            int height = histogram[x];
            while (true)
            {
                if (stack.Count == 0 || height > stack.Peek().Item2)
                {
                    stack.Push(new Tuple<int, int>(start, height));
                }
                else if (height < stack.Peek().Item2)
                {
                    int tempArea = (int)(stack.Peek().Item2 * (x - stack.Peek().Item1));
                    if (tempArea > maxArea)
                    {
                        YStart = stack.Peek().Item1;
                        maxSize = new Tuple<int, int>(stack.Peek().Item2, (x - stack.Peek().Item1));
                        maxArea = tempArea;
                    }
                    Tuple<int, int> popped = stack.Pop();
                    start = (int)popped.Item1;
                    continue;
                }
                break;
            }
        }

        foreach (Tuple<int, int> data in stack)
        {
            int tempArea = (int)(data.Item2 * (x - data.Item1));
            if (tempArea > maxArea)
            {
                YStart = data.Item1;
                maxSize = new Tuple<int, int>(data.Item2, (x - data.Item1));
                maxArea = tempArea;
            }
        }

        return maxSize;
    }