Вопрос:

Головоломка: Найти самый большой прямоугольник (проблема максимального прямоугольника)

algorithm language-agnostic math geometry

26093 просмотра

7 ответа

22014 Репутация автора

Какой самый эффективный алгоритм поиска прямоугольника с наибольшей площадью, который поместится в пустом пространстве?

Допустим, экран выглядит так («#» представляет заполненную область):

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

Возможное решение:

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

Обычно я бы с удовольствием нашел решение. Хотя в этот раз я бы хотел не тратить время на самостоятельную работу, поскольку это имеет практическое применение для проекта, над которым я работаю. Есть ли известное решение?

Shog9 написал (а):

Является ли ваш вход массивом (как подразумевается другими ответами) или списком окклюзий в форме позиционированных прямоугольников произвольного размера (как может иметь место в оконной системе при работе с позициями окна)?

Да, у меня есть структура, которая отслеживает набор окон, размещенных на экране. У меня также есть сетка, которая отслеживает все области между каждым ребром, являются ли они пустыми или заполненными, и положение в пикселях их левого или верхнего края. Я думаю, что есть какая-то измененная форма, которая бы использовала это свойство. Вы знаете что-нибудь?

Автор: Mark Renouf Источник Размещён: 10.08.2008 05:16

Ответы (7)


4 плюса

294824 Репутация автора

Вот страница с кодом и анализом.

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

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

Автор: Lasse Vågsæther Karlsen Размещён: 10.08.2008 05:23

2 плюса

22014 Репутация автора

@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++) {

ХАХА ... O (m2 n2) .. Это, наверное, то, что я бы придумал.

Я вижу, они продолжают разрабатывать оптимизацию ... выглядит хорошо, я прочитаю.

Автор: Mark Renouf Размещён: 10.08.2008 05:30

20 плюса

22014 Репутация автора

Решение

@lassevk

Я нашел ссылочную статью из DDJ: проблема максимального прямоугольника

Автор: Mark Renouf Размещён: 10.08.2008 05:44

21 плюса

691 Репутация автора

Я являюсь автором этой статьи доктора Добба, и меня иногда спрашивают о реализации. Вот простой в 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;
}

Он берет свой вклад из консоли. Вы можете, например, передать этот файл к нему:

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

И после печати его ввода, он выведет:

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

Вышеприведенная реализация, конечно, ничего особенного, но она очень близка к объяснению в статье доктора Добба и должна быть легко переведена на то, что нужно.

Автор: Daveed V. Размещён: 18.11.2013 02:20

2 плюса

81 Репутация автора

Я реализовал решение Доббса в Java.

Никаких гарантий ни на что.

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

}
Автор: Spike2050 Размещён: 23.06.2016 02:19

2 плюса

526 Репутация автора

После долгих попыток я написал этот алгоритм ... Просто посмотрите код ...

Вы понимаете это. Этот код говорит !!

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);
    }
}
Автор: bharath Размещён: 06.08.2017 06:01

0 плюса

8145 Репутация автора

Я являюсь автором Maximal Rectangle Solution на LeetCode, на котором основан этот ответ.

Поскольку решение на основе стека уже обсуждалось в других ответах, я хотел бы представить оптимальное O(NM)решение для динамического программирования, созданное пользователем morrischen2008 .

Интуиция

Представьте себе алгоритм, в котором для каждой точки мы вычисляли прямоугольник, выполняя следующие действия:

  • Нахождение максимальной высоты прямоугольника путем итерации вверх, пока не будет достигнута заполненная область

  • Нахождение максимальной ширины прямоугольника путем итерации влево и вправо до высоты, которая не соответствует максимальной высоте прямоугольника

Например, найти прямоугольник, определенный желтой точкой: введите описание изображения здесь

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

Для каждой точки мы определяем некоторые переменные:

h - высота прямоугольника, определенного этой точкой

l - левая граница прямоугольника, определенного этой точкой

r - правая граница прямоугольника, определенного этой точкой

Эти три переменные однозначно определяют прямоугольник в этой точке. Мы можем вычислить площадь этого прямоугольника с помощью h * (r - l). Глобальный максимум всех этих областей - наш результат.

Использование динамического программирования, мы можем использовать h, lи rкаждую точку в предыдущей строке , чтобы вычислить h, lи rдля каждой точки в следующей строке в линейное время.

Алгоритм

Учитывая ряд matrix[i], мы отслеживаем из h, lи rкаждой точки в строке, определяя три массива - height, leftи right.

height[j]будет соответствовать высоте matrix[i][j], и так далее, и так далее с другими массивами.

Теперь возникает вопрос, как обновить каждый массив.

height

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

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

left:

Посмотрите, что вызывает изменения левой границы нашего прямоугольника. Поскольку все экземпляры заполненных пробелов, встречающиеся в строке выше текущей, уже включены в текущую версию left, единственное, что влияет на нашу версию , left- это если мы встретим заполненную пробел в нашей текущей строке.

В результате мы можем определить:

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

cur_leftэто одно больше, чем крайнее правое заполненное пространство, с которым мы столкнулись. Когда мы «расширяем» прямоугольник влево, мы знаем, что он не может расширяться после этой точки, иначе он попадет в заполненное пространство.

right:

Здесь мы можем повторно использовать наши рассуждения leftи определить:

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

cur_right самое левое вхождение заполненного пространства, с которым мы столкнулись.

Реализация

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
Автор: Primusa Размещён: 17.04.2019 12:51
Вопросы из категории :
32x32