algorithm - tamaño - Encuentra el rectángulo más grande que contiene solo ceros en una matriz binaria N × N

propiedades de los determinantes

Question

Dada una matriz binaria NxN (que contiene solo 0 o 1), ¿cómo podemos encontrar el rectángulo más grande que contenga todos los 0?

Ejemplo:

      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 

Para el ejemplo anterior, es una matriz binaria de 6 × 6. el valor de retorno en este caso será la Celda 1: (2, 1) y la Celda 2: (4, 4). La submatriz resultante puede ser cuadrada o rectangular. El valor de retorno también puede ser el tamaño de la submatriz más grande de todos los 0, en este ejemplo 3 × 4.

Answer 1

Aquí está el método JF Sebastians traducido a 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;            
    }

Algunas cosas para tener en cuenta sobre esto:

1. Esta versión está pensada para ser utilizada con la API de Unity. Puede hacer que esto sea más genérico reemplazando instancias de Vector2 con KeyValuePair. Vector2 solo se usa para una forma conveniente de almacenar dos valores.
2. invalidPoints [] es una matriz de bool, donde verdadero significa que el punto de la grilla está "en uso" y falso significa que no lo es.

Answer 2

Aquí hay una solución Python3, que devuelve la posición además del área del rectángulo más grande:

#!/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))

Salida:

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

Answer 3

Aquí hay una solución basada en el problema "Rectangular más grande en un histograma" sugerida por @j_random_hacker en los comentarios:

[Algoritmo] funciona iterando a través de las filas de arriba a abajo, para cada fila que resuelve este problema , donde las "barras" en el "histograma" consisten en todos los trazados ascendentes de ceros que comienzan en la fila actual (una columna tiene altura 0 si tiene un 1 en la fila actual).

La matriz de matriz de entrada puede ser iterativa arbitraria, por ejemplo, un archivo o una secuencia de red. Solo se requiere una fila para estar disponible a la vez.

#!/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)

La solución es O(N) , donde N es el número de elementos en una matriz. Requiere O(ncols) memoria adicional, donde ncols es el número de columnas en una matriz.

La última versión con pruebas está en https://gist.github.com/776423

Answer 4

Mire Maximice el área rectangular debajo de Histograma y luego continúe leyendo la solución a continuación.

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.

La complejidad del tiempo es O (N * N) = O (N²) (para una matriz binaria NxN)

Ejemplo:

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 5

Propongo un método O (nxn).

Primero, puedes listar todos los rectángulos vacíos máximos. Vacío significa que cubre solo 0s. Un rectángulo vacío máximo es tal que no se puede extender en una dirección sin cubrir (al menos) uno 1.

Puede encontrar un documento que presente un algoritmo O (nxn) para crear dicha lista en www.ulg.ac.be/telecom/rectangles , así como en el código fuente (no optimizado). No es necesario almacenar la lista, es suficiente llamar a una función de devolución de llamada cada vez que el algoritmo encuentre un rectángulo, y almacenar solo el más grande (o elija otro criterio si lo desea).

Tenga en cuenta que existe una prueba (ver el artículo) de que el número de rectángulos vacíos más grandes está limitado por el número de píxeles de la imagen (nxn en este caso).

Por lo tanto, seleccionar el rectángulo óptimo se puede hacer en O (nxn), y el método general también es O (nxn).

En la práctica, este método es muy rápido y se usa para el análisis de flujo de video en tiempo real.

Answer 6

Solución con complejidad de espacio O (columnas) [Se puede modificar a O (filas) también] y complejidad de tiempo O (filas * columnas)

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

Pero obtengo Time Limite excedido excpetion cuando pruebo esto en LeetCode. ¿Hay alguna solución menos compleja?