Frage

Was ist der effizienteste Algorithmus, um das Rechteck mit der größten Fläche zu finden, das in den leeren Raum passt?

Nehmen wir an, der Bildschirm sieht so aus ('#' steht für einen gefüllten Bereich):

....................
..............######
##..................
.................###
.................###
#####...............
#####...............
#####...............

Eine wahrscheinliche Lösung ist:

....................
..............######
##...++++++++++++...
.....++++++++++++###
.....++++++++++++###
#####++++++++++++...
#####++++++++++++...
#####++++++++++++...

Normalerweise würde es mir Spaß machen, eine Lösung zu finden.Allerdings möchte ich dieses Mal vermeiden, Zeit damit zu verschwenden, alleine herumzufummeln, da dies für ein Projekt, an dem ich arbeite, einen praktischen Nutzen hat.Gibt es eine bekannte Lösung?

Shog9 schrieb:

Ist Ihre Eingabe ein Array (wie aus den anderen Antworten hervorgeht) oder eine Liste von Verdeckungen in Form von beliebig großen, positionierten Rechtecken (wie es in einem Fenstersystem der Fall sein könnte, wenn es um Fensterpositionen geht)?

Ja, ich habe eine Struktur, die eine Reihe von auf dem Bildschirm platzierten Fenstern verfolgt.Ich habe auch ein Raster, das alle Bereiche zwischen den einzelnen Kanten verfolgt, unabhängig davon, ob sie leer oder gefüllt sind, sowie die Pixelposition ihrer linken oder oberen Kante.Ich denke, es gibt eine modifizierte Form, die diese Eigenschaft ausnutzen würde.Kennen Sie welche?

War es hilfreich?

Lösung 2

@lassevk

Ich habe den Artikel, auf den verwiesen wird, von DDJ gefunden: Das Problem des maximalen Rechtecks

Andere Tipps

Ich bin der Autor davon, Dr.Dobbs Artikel und werde gelegentlich nach einer Implementierung gefragt.Hier ist eine einfache in 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;
}

Die Eingabe erfolgt über die Konsole.Sie könnten z.B.Pipe diese Datei dorthin:

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

Und nach dem Drucken der Eingabe wird Folgendes ausgegeben:

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

Die obige Implementierung ist natürlich nichts Besonderes, aber sie kommt der Erklärung im Dr. sehr nahe.Dobbs Artikel und sollte leicht in alles zu übersetzen sein, was benötigt wird.

Hier ist eine Seite mit Code und Analysen.

Ihr spezielles Problem beginnt etwas weiter unten auf der Seite. Durchsuchen Sie die Seite nach dem Text Maximales Rechteckproblem.

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

@lassevk

    // 4. Outer double-for-loop to consider all possible positions 
    //    for topleft corner. 
    for (int i=0; i < M; i++) {
      for (int j=0; j < N; j++) {

        // 2.1 With (i,j) as topleft, consider all possible bottom-right corners. 

        for (int a=i; a < M; a++) {
          for (int b=j; b < N; b++) {

HAHA...O(m2 n2)..Das wäre wahrscheinlich das, was ich mir ausgedacht hätte.

Ich sehe, dass sie weiterhin Optimierungen entwickeln ...Sieht gut aus, ich werde es lesen.

Ich habe die Lösung von Dobbs in Java implementiert.

Keine Garantie für irgendetwas.

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

}

Nach so viel Mühe habe ich diesen Algorithmus geschrieben ... Schauen Sie sich einfach den Code an ...

Du verstehst das. Dieser Code spricht!!

import java.util.Scanner;
import java.util.Stack;

/**
 * Created by BK on 05-08-2017.
 */
public class LargestRectangleUnderHistogram {
    public static void main(String... args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] input = new int[n];
        for (int j = 0; j < n; j++) {
            input[j] = scanner.nextInt();
        }



        /*
        *   This is the procedure used for solving :
        *
        *   Travel from first element to last element of the array
        *
        *   If stack is empty add current element to stack
        *
        *   If stack is not empty check for the top element of stack if
        *   it is smaller than the current element push into stack
        *
        *   If it is larger than the current element pop the stack until we get an
        *   element smaller than the current element or until stack becomes empty
        *
        *   After popping each element check if the stack is empty or not..
        *
        *   If stack is empty it means that this is the smallest element encountered till now
        *
        *   So we can multiply i with this element to get a big rectangle which is contributed by
        *
        *   this
        *
        *   If stack is not empty then check for individual areas(Not just one bar individual area means largest rectangle by this) (i-top)*input[top]
        *
        *
        * */

        /*
        * Initializing the maxarea as we check each area with maxarea
        */

        int maxarea = -1;
        int i = 0;
        Stack<Integer> stack = new Stack<>();
        for (i = 0; i < input.length; i++) {

            /*
            *   Pushing the element if stack is empty
            * */


            if (stack.isEmpty()) {
                stack.push(i);
            } else {

                /*
                *   If stack top element is less than current element push
                * */

                if (input[stack.peek()] < input[i]) {
                    stack.push(i);
                } else {

                    /*
                    *   Else pop until we encounter an element smaller than this in stack or stack becomes empty
                    *   
                    * */


                    while (!stack.isEmpty() && input[stack.peek()] > input[i]) {

                        int top = stack.pop();

                        /*
                        *   If stack is empty means this is the smallest element encountered so far
                        *   
                        *   So we can multiply this with i
                        * */

                        if (stack.isEmpty()) {
                            maxarea = maxarea < (input[top] * i) ? (input[top] * i) : maxarea;
                        }

                        /*
                         *  If stack is not empty we find areas of each individual rectangle
                         *  Remember we are in while loop
                         */

                        else {
                            maxarea = maxarea < (input[top] * (i - top)) ? (input[top] * (i - top)) : maxarea;
                        }
                    }
                    /*
                    *   Finally pushing the current element to stack
                    * */

                    stack.push(i);
                }
            }
        }

        /*
        *  This is for checking if stack is not empty after looping the last element of input
        *  
        *  This happens if input is like this 4 5 6 1 2 3 4 5
        *  
        *  Here 2 3 4 5 remains in stack as they are always increasing and we never got 
        *  
        *  a chance to pop them from stack by above process
        *  
        * */


        while (!stack.isEmpty()) {

            int top = stack.pop();

            maxarea = maxarea < (i - top) * input[top] ? (i - top) * input[top] : maxarea;
        }

        System.out.println(maxarea);
    }
}

Ich bin der Autor des Maximale Rechtecklösung auf LeetCode, worauf diese Antwort basiert.

Da die Stack-basierte Lösung bereits in den anderen Antworten besprochen wurde, möchte ich hier eine optimale Lösung vorstellen O(NM) dynamische Programmierlösung, die vom Benutzer stammt morrischen2008.

Intuition

Stellen Sie sich einen Algorithmus vor, bei dem wir für jeden Punkt ein Rechteck berechnen, indem wir Folgendes tun:

  • Ermitteln der maximalen Höhe des Rechtecks, indem nach oben iteriert wird, bis ein gefüllter Bereich erreicht ist

  • Finden Sie die maximale Breite des Rechtecks, indem Sie nach links und rechts nach außen iterieren, bis eine Höhe erreicht ist, die nicht mehr der maximalen Höhe des Rechtecks ​​entspricht

Zum Beispiel das durch den gelben Punkt definierte Rechteck finden:enter image description here

Wir wissen, dass das maximale Rechteck eines der auf diese Weise konstruierten Rechtecke sein muss (das maximale Rechteck muss einen Punkt auf seiner Basis haben, an dem sich das nächste gefüllte Quadrat befindet). Höhe oberhalb dieses Punktes).

Für jeden Punkt definieren wir einige Variablen:

h - die Höhe des durch diesen Punkt definierten Rechtecks

l - die linke Grenze des durch diesen Punkt definierten Rechtecks

r - die rechte Grenze des durch diesen Punkt definierten Rechtecks

Diese drei Variablen definieren das Rechteck an diesem Punkt eindeutig.Wir können die Fläche dieses Rechtecks ​​mit berechnen h * (r - l).Das globale Maximum all dieser Bereiche ist unser Ergebnis.

Mit dynamischer Programmierung können wir das verwenden h, l, Und r jedes Punktes in der vorherigen Zeile, um die zu berechnen h, l, Und r für jeden Punkt in der nächsten Zeile in linearer Zeit.

Algorithmus

Gegebene Zeile matrix[i], wir behalten den Überblick h, l, Und r jedes Punktes in der Zeile durch die Definition von drei Arrays - height, left, Und right.

height[j] entspricht der Höhe von matrix[i][j], und so weiter und so weiter mit den anderen Arrays.

Nun stellt sich die Frage, wie jedes Array aktualisiert wird.

height

h ist definiert als die Anzahl der zusammenhängenden unbefüllten Leerzeichen in einer Linie von unserem Punkt aus.Wir erhöhen den Wert, wenn es einen neuen Raum gibt, und setzen ihn auf Null, wenn der Raum gefüllt ist (wir verwenden „1“, um einen leeren Raum anzuzeigen, und „0“, um einen gefüllten Raum anzuzeigen).

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

left:

Überlegen Sie, was Änderungen an der linken Grenze unseres Rechtecks ​​verursacht.Da alle Instanzen gefüllter Leerzeichen, die in der Zeile über der aktuellen vorkommen, bereits in der aktuellen Version von berücksichtigt wurden left, das Einzige, was uns betrifft left ist, wenn wir in unserer aktuellen Zeile auf ein gefülltes Leerzeichen stoßen.

Als Ergebnis können wir Folgendes definieren:

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

cur_left ist ein größerer als der ganz rechts ausgefüllte Raum, auf den wir gestoßen sind.Wenn wir das Rechteck nach links „erweitern“, wissen wir, dass es nicht über diesen Punkt hinaus erweitert werden kann, da es sonst in den gefüllten Raum hineinläuft.

right:

Hier können wir unsere Argumentation wiederverwenden left und definieren:

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

cur_right ist das Vorkommen eines gefüllten Raums ganz links, auf den wir gestoßen sind.

Implementierung

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
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top