퍼즐:가장 큰 직사각형 찾기 (최대 직사각형 문제)
-
08-06-2019 - |
문제
빈 공간에 들어갈 수 있는 가장 큰 면적을 가진 직사각형을 찾는 가장 효율적인 알고리즘은 무엇입니까?
화면이 다음과 같다고 가정해 보겠습니다('#'은 채워진 영역을 나타냄).
....................
..............######
##..................
.................###
.................###
#####...............
#####...............
#####...............
가능한 해결책은 다음과 같습니다.
....................
..............######
##...++++++++++++...
.....++++++++++++###
.....++++++++++++###
#####++++++++++++...
#####++++++++++++...
#####++++++++++++...
일반적으로 나는 해결책을 찾는 것을 좋아합니다.이번에는 제가 진행 중인 프로젝트에 실용적인 용도가 있기 때문에 혼자서 더듬으며 시간을 낭비하는 것은 피하고 싶습니다.잘 알려진 해결책이 있나요?
쇼그9 썼다:
입력이 배열(다른 응답에서 암시된 바와 같이)입니까, 아니면 임의로 크기가 지정되고 위치가 지정된 직사각형 형태의 폐색 목록입니까(창 위치를 처리할 때 윈도우 시스템의 경우일 수 있음)?
예, 화면에 배치된 창 세트를 추적하는 구조가 있습니다.또한 각 가장자리 사이의 모든 영역(비어 있는지 또는 채워졌는지 여부)과 왼쪽 또는 위쪽 가장자리의 픽셀 위치를 추적하는 그리드도 있습니다.나는 이 속성을 활용할 수 있는 몇 가지 수정된 형태가 있다고 생각합니다.혹시 알고 계시나요?
해결책 2
@lassevk
DDJ에서 참조 기사를 찾았습니다. 최대 직사각형 문제
다른 팁
저는 그 박사님의 저자입니다.Dobb의 기사를 참조하고 가끔 구현에 대한 질문을 받습니다.다음은 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]
위의 구현은 물론 화려하지는 않지만 Dr.의 설명과 매우 유사합니다.Dobb의 기사는 필요한 모든 내용으로 쉽게 번역할 수 있어야 합니다.
다음은 몇 가지 코드와 분석이 포함된 페이지입니다.
특정 문제는 페이지의 약간 아래에서 시작됩니다. 페이지에서 텍스트를 검색하세요. 최대 직사각형 문제.
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++) {
ㅋ...오(m2·n2)..아마도 내가 생각 해낸 것입니다.
계속해서 최적화를 개발하는 것을 봅니다...좋은 것 같아요, 읽어보겠습니다.
Java로 Dobbs 솔루션을 구현했습니다.
아무것도 보증하지 않습니다.
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);
}
}
많은 어려움을 겪은 끝에 이 알고리즘을 작성했습니다... 코드를 보세요...
당신은 그것을 이해합니다.이 코드는 말합니다 !!
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);
}
}
나는 최대 직사각형 솔루션 이 답변의 기반은 LeetCode입니다.
스택 기반 솔루션은 이미 다른 답변에서 논의되었으므로 최적의 솔루션을 제시하고 싶습니다. O(NM)
사용자로부터 시작되는 동적 프로그래밍 솔루션 모리셴2008.
직관
각 점에 대해 다음을 수행하여 직사각형을 계산하는 알고리즘을 상상해 보십시오.
채워진 영역에 도달할 때까지 위쪽으로 반복하여 직사각형의 최대 높이 찾기
직사각형의 최대 높이를 수용하지 않는 높이까지 왼쪽과 오른쪽 바깥쪽으로 반복하여 직사각형의 최대 너비를 찾습니다.
예를 들어 노란색 점으로 정의된 직사각형을 찾는 경우:
우리는 최대 직사각형이 이런 방식으로 구성된 직사각형 중 하나여야 한다는 것을 알고 있습니다. (최대 직사각형은 다음으로 채워진 정사각형이 있는 밑면에 점이 있어야 합니다. 키 그 지점 이상).
각 지점에 대해 몇 가지 변수를 정의합니다.
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
우리 지점에서 한 줄로 채워지지 않은 연속 공간의 수로 정의됩니다.새로운 공간이 있으면 증가하고 공간이 채워지면 0으로 설정합니다('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
우리가 접했던 가장 오른쪽의 채워진 공간보다 1 더 큽니다.직사각형을 왼쪽으로 "확장"하면 해당 지점을 지나서 확장될 수 없다는 것을 알 수 있습니다. 그렇지 않으면 채워진 공간으로 실행될 것입니다.
right
:
여기서 우리는 추론을 재사용할 수 있습니다. left
다음을 정의합니다.
new_right[j] = min(old_right[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