Puzzle: Trouver plus grand rectangle (maximale rectangle de problème)

Je suis l'auteur de ce Dr Dobb's article et d'obtenir parfois posé des questions sur la mise en œuvre. Voici un exemple simple d'un dans C:

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int one;
  int two;
} Pair;

Pair best_ll = { 0, 0 };
Pair best_ur = { -1, -1 };
int best_area = 0;

int *c; /* Cache */
Pair *s; /* Stack */
int top = 0; /* Top of stack */

void push(int a, int b) {
  s[top].one = a;
  s[top].two = b;
  ++top;
}

void pop(int *a, int *b) {
  --top;
  *a = s[top].one;
  *b = s[top].two;
}


int M, N; /* Dimension of input; M is length of a row. */

void update_cache() {
  int m;
  char b;
  for (m = 0; m!=M; ++m) {
    scanf(" %c", &b);
    fprintf(stderr, " %c", b);
    if (b=='0') {
      c[m] = 0;
    } else { ++c[m]; }
  }
  fprintf(stderr, "\n");
}


int main() {
  int m, n;
  scanf("%d %d", &M, &N);
  fprintf(stderr, "Reading %dx%d array (1 row == %d elements)\n", M, N, M);
  c = (int*)malloc((M+1)*sizeof(int));
  s = (Pair*)malloc((M+1)*sizeof(Pair));
  for (m = 0; m!=M+1; ++m) { c[m] = s[m].one = s[m].two = 0; }
  /* Main algorithm: */
  for (n = 0; n!=N; ++n) {
    int open_width = 0;
    update_cache();
    for (m = 0; m!=M+1; ++m) {
      if (c[m]>open_width) { /* Open new rectangle? */
        push(m, open_width);
        open_width = c[m];
      } else /* "else" optional here */
      if (c[m]<open_width) { /* Close rectangle(s)? */
        int m0, w0, area;
        do {
          pop(&m0, &w0);
          area = open_width*(m-m0);
          if (area>best_area) {
            best_area = area;
            best_ll.one = m0; best_ll.two = n;
            best_ur.one = m-1; best_ur.two = n-open_width+1;
          }
          open_width = w0;
        } while (c[m]<open_width);
        open_width = c[m];
        if (open_width!=0) {
          push(m0, w0);
        }
      }
    }
  }
  fprintf(stderr, "The maximal rectangle has area %d.\n", best_area);
  fprintf(stderr, "Location: [col=%d, row=%d] to [col=%d, row=%d]\n",
                  best_ll.one+1, best_ll.two+1, best_ur.one+1, best_ur.two+1);
  return 0;
}

Il prend son entrée, à partir de la console. Vous pourriez par exemple tuyau de ce fichier:

16 12
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 0
0 0 0 1 1 0 1 1 1 0 1 1 1 0 1 0
0 0 0 0 1 1 * * * * * * 0 0 1 0
0 0 0 0 0 0 * * * * * * 0 0 1 0
0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 0
0 0 1 0 0 0 0 1 0 0 1 1 1 0 1 0 
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0

Et après l'impression de son entrée, il sera de sortie:

The maximal rectangle has area 12.
Location: [col=7, row=6] to [col=12, row=5]

La mise en œuvre ci-dessus est rien de compliqué, bien sûr, mais c'est très proche de l'explication du Dr Dobb's de l'article et doit être facile à traduire tout ce qui est nécessaire.

Voici une page qui a un peu de code et l'analyse.

De votre problème commence un peu vers le bas sur la page, la recherche de la page pour le texte maximale rectangle problème.

http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module6/module6.html

J'ai mis en place la solution de Dobbs en Java.

Aucune garantie de quoi que ce soit.

package com.test;

import java.util.Stack;

public class Test {

    public static void main(String[] args) {
        boolean[][] test2 = new boolean[][] { new boolean[] { false, true, true, false },
                new boolean[] { false, true, true, false }, new boolean[] { false, true, true, false },
                new boolean[] { false, true, false, false } };
        solution(test2);
    }

    private static class Point {
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int x;
        public int y;
    }

    public static int[] updateCache(int[] cache, boolean[] matrixRow, int MaxX) {
        for (int m = 0; m < MaxX; m++) {
            if (!matrixRow[m]) {
                cache[m] = 0;
            } else {
                cache[m]++;
            }
        }
        return cache;
    }

    public static void solution(boolean[][] matrix) {
        Point best_ll = new Point(0, 0);
        Point best_ur = new Point(-1, -1);
        int best_area = 0;

        final int MaxX = matrix[0].length;
        final int MaxY = matrix.length;

        Stack<Point> stack = new Stack<Point>();
        int[] cache = new int[MaxX + 1];

        for (int m = 0; m != MaxX + 1; m++) {
            cache[m] = 0;
        }

        for (int n = 0; n != MaxY; n++) {
            int openWidth = 0;
            cache = updateCache(cache, matrix[n], MaxX);
            for (int m = 0; m != MaxX + 1; m++) {
                if (cache[m] > openWidth) {
                    stack.push(new Point(m, openWidth));
                    openWidth = cache[m];
                } else if (cache[m] < openWidth) {
                    int area;
                    Point p;
                    do {
                        p = stack.pop();
                        area = openWidth * (m - p.x);
                        if (area > best_area) {
                            best_area = area;
                            best_ll.x = p.x;
                            best_ll.y = n;
                            best_ur.x = m - 1;
                            best_ur.y = n - openWidth + 1;
                        }
                        openWidth = p.y;
                    } while (cache[m] < openWidth);
                    openWidth = cache[m];
                    if (openWidth != 0) {
                        stack.push(p);
                    }
                }
            }
        }

        System.out.printf("The maximal rectangle has area %d.\n", best_area);
        System.out.printf("Location: [col=%d, row=%d] to [col=%d, row=%d]\n", best_ll.x + 1, best_ll.y + 1,
                best_ur.x + 1, best_ur.y + 1);
    }

}

Je suis l'auteur de la Maximale Rectangle Solution sur LeetCode, qui est ce que cette réponse est fondée sur.

Depuis la pile, la solution a déjà été discuté dans les autres réponses, je voudrais présenter une optimale O(NM) de la programmation dynamique solution qui provient de l'utilisateur morrischen2008.

Intuition

Imaginer un algorithme dans lequel, pour chaque point, nous avons calculé un rectangle en procédant de la manière suivante:

• Trouver le maximum de la hauteur du rectangle par l'itération vers le haut jusqu'à ce qu'une zone remplie est atteint

• Trouver le maximum de la largeur du rectangle par l'itération vers l'extérieur à gauche et à droite jusqu'à une hauteur qui ne veut pas accueillir la hauteur maximale du rectangle

Par exemple trouver le rectangle défini par le point jaune:

Nous savons que l'maximale du rectangle doit être l'un des rectangles construits de cette manière (le max rectangle doit avoir un point sur sa base, où le prochain carré plein est hauteur au-dessus de ce point).

Pour chaque point, on définit des variables:

h - la hauteur du rectangle défini par ce point

l - la bande gauche du rectangle défini par ce point

r - la bande droite du rectangle défini par ce point

Ces trois variables définissent de façon unique le rectangle en ce point. Nous pouvons calculer l'aire de ce rectangle avec h * (r - l). Le maximum global de tous ces domaines est de notre résultat.

Utilisant la programmation dynamique, nous pouvons utiliser la h, l, et r de chaque point de la ligne précédente pour calculer la h, l, et r pour chaque point dans la ligne suivante dans le temps linéaire.

Algorithme

Ligne donnée matrix[i], nous gardons la trace de la h, l, et r de chaque point de la ligne par la définition des trois tableaux - height, left, et right.

height[j] correspondra à la hauteur de matrix[i][j], et ainsi de suite et ainsi de suite avec les autres tableaux.

La question devient maintenant comment mettre à jour chaque tableau.

height

h est défini comme le nombre de continue espaces vacants dans un ligne à partir de notre point. On incrémente le compteur si il y a un nouvel espace, et de mettre zéro si l'espace est rempli (nous sommes à l'aide de " 1 " pour indiquer un espace vide et '0' comme un rempli un).

new_height[j] = old_height[j] + 1 if row[j] == '1' else 0

left:

Considérons quelles sont les causes des changements à la gauche de la lie de notre rectangle. Depuis toutes les instances des espaces remplis survenant dans la ligne au-dessus de l'actuel ont déjà été pris en compte dans la version actuelle de left, la seule chose qui affecte notre left est si on rencontre un espace rempli dans notre ligne actuelle.

Ainsi, nous pouvons définir:

new_left[j] = max(old_left[j], cur_left)

cur_left est plus grand que la plus à droite, rempli de l'espace, nous l'avons rencontré. Lorsque nous "élargir" le rectangle de gauche, nous savons qu'il est impossible d'étendre delà de ce point, sinon ça va fonctionner dans l'espace rempli.

right:

Ici, nous pouvons réutiliser notre raisonnement dans left et de définir:

new_right[j] = min(old_right[j], cur_right)

cur_right est le plus à gauche survenance d'un espace rempli, nous l'avons rencontré.

Mise en œuvre

def maximalRectangle(matrix):
    if not matrix: return 0

    m = len(matrix)
    n = len(matrix[0])

    left = [0] * n # initialize left as the leftmost boundary possible
    right = [n] * n # initialize right as the rightmost boundary possible
    height = [0] * n

    maxarea = 0

    for i in range(m):

        cur_left, cur_right = 0, n
        # update height
        for j in range(n):
            if matrix[i][j] == '1': height[j] += 1
            else: height[j] = 0
        # update left
        for j in range(n):
            if matrix[i][j] == '1': left[j] = max(left[j], cur_left)
            else:
                left[j] = 0
                cur_left = j + 1
        # update right
        for j in range(n-1, -1, -1):
            if matrix[i][j] == '1': right[j] = min(right[j], cur_right)
            else:
                right[j] = n
                cur_right = j
        # update the area
        for j in range(n):
            maxarea = max(maxarea, height[j] * (right[j] - left[j]))

    return maxarea