首页 / 知识

关于算法：拼图：找到最大矩形(最大矩形问题)

2023-04-11 23:29:00

Puzzle: Find largest rectangle (maximal rectangle problem)

找到面积最大的矩形适合空空间的最有效算法是什么？

假设屏幕看起来像这样("＃"代表填充区域)：

1
2
3
4
5
6
7
8

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

一个可能的解决方案是：

1
2
3
4
5
6
7
8

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

通常，我很乐于找出解决方案。尽管这一次我想避免浪费自己的时间，因为这对于我正在从事的项目具有实际用途。有众所周知的解决方案吗？

Shog9写道：

Is your input an array (as implied by the other responses), or a list of occlusions in the form of arbitrarily sized, positioned rectangles (as might be the case in a windowing system when dealing with window positions)?

是的，我有一个结构，可以跟踪屏幕上放置的一组窗口。我还有一个网格，可以跟踪每个边缘之间的所有区域(无论它们是空的还是填充的)以及它们左边缘或上边缘的像素位置。我认为有一些修改后的表单可以利用此属性。你知道吗

我是Dobb博士文章的作者，偶尔??会被问到一个实现。这是C语言中的一个简单示例：

#include
#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,"
");
}

int main() {
int m, n;
scanf("%d %d", &M, &N);
fprintf(stderr,"Reading %dx%d array (1 row == %d elements)
", 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.
", best_area);
fprintf(stderr,"Location: [col=%d, row=%d] to [col=%d, row=%d]
",
best_ll.one+1, best_ll.two+1, best_ur.one+1, best_ur.two+1);
return 0;
}

它从控制台获取输入。您可以例如将此文件传递给它：

1
2
3
4
5
6
7
8
9
10
11
12
13

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

在打印输入后，它将输出：

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

上面的实现当然没什么花哨的，但是它与Dobb博士的文章中的解释非常接近，应该容易地转换为所需的一切。

@lassevk

我从DDJ找到了引用的文章：最大矩形问题

这是一个包含一些代码和分析的页面。

您的特定问题在页面上开始有点向下，在页面上搜索文本最大矩形问题。

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

我是LeetCode上的最大矩形解决方案的作者，这是此答案的基础。

由于在其他答案中已经讨论了基于堆栈的解决方案，因此我想提出一种源自用户morrischen2008的最佳O(NM)动态编程解决方案。

直觉

想象一个算法，对于每个点，我们通过执行以下操作来计算一个矩形：

通过向上迭代直到达到填充区域来找到矩形的最大高度
通过向左和向右向外迭代直到不适应矩形最大高度的高度来找到矩形的最大宽度

例如，找到由黄点定义的矩形：
enter image description here

我们知道最大矩形必须是以此方式构造的矩形之一(最大矩形的底边必须有一个点，下一个实心正方形是该点上方的高度)。

对于每个点，我们定义一些变量：

h-该点定义的矩形的高度

l-该点定义的矩形的左边界

r-该点定义的矩形的右边界

这三个变量在该点唯一定义矩形。我们可以使用h * (r - l)计算该矩形的面积。所有这些领域的全球最大值是我们的结果。

使用动态编程，我们可以使用上一行中每个点的h，l和r来计算下一行中每个点的h，l和r线性时间。

算法

给定行matrix[i]，我们通过定义三个数组-height，left和right来跟踪行中每个点的h，l和r。

height[j]将对应于matrix[i][j]的高度，以此类推，以此类推。

现在的问题是如何更新每个阵列。

height

h定义为从我们的角度来看，一行中连续的未填充空格的数量。如果有一个新的空间，我们将递增；如果该空间已被填充，则将其设置为零(我们使用" 1"表示空白，而使用" 0"表示填充的空间)。

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

left:

考虑是什么导致矩形的左边界发生变化。由于在当前行上方的行中出现的所有填充空间实例已被纳入当前版本的left中，因此唯一影响我们left的因素是在当前行中遇到填充空间。

结果，我们可以定义：

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

cur_left比我们遇到的最右边的填充空间大一个。当我们"扩展"矩形到左侧时，我们知道它不能扩展到该点之外，否则它将进入填充的空间。

right:

在这里，我们可以在left中重用我们的推理并定义：

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

cur_right是我们遇到的填充空间的最左端。

实作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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

经过这么多的努力后，我已经写了这个算法...只看代码...

您理解这一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

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

我用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.
", best_area);
System.out.printf("Location: [col=%d, row=%d] to [col=%d, row=%d]
", best_ll.x + 1, best_ll.y + 1,
best_ur.x + 1, best_ur.y + 1);
}

}

@lassevk

1
2
3
4
5
6
7
8
9

// 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)..那可能就是我想要的。

我看到他们继续进行优化...看起来不错，我会读一读。

算法区域屏幕填充