拼图:找到最大的矩形(最大矩形问题)

Question

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

假设屏幕看起来像这样('#'代表填充区域):

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

一个可能的解决方案是:

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

通常我会喜欢找出解决方案.虽然这次我想避免浪费时间自己摸索,因为这对我正在研究的项目有实际用途.有一个众所周知的解决方案吗？

Shog9写道:

您的输入是一个数组(如其他响应所暗示的那样),还是一个以任意大小的定位矩形形式的遮挡列表(在处理窗口位置时窗口系统中可能就是这种情况)？

是的,我有一个跟踪屏幕上放置的一组窗口的结构.我还有一个网格,可以跟踪每条边之间的所有区域,无论它们是空的还是填充的,以及它们左边或顶边的像素位置.我认为有一些修改后的形式可以利用这个属性.你知道吗？

Answer 1

我是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]

上面的实现当然没什么特别的,但是它与Dobb博士的文章中的解释非常接近,应该很容易转化为所需要的东西.

Answer 2

@lassevk

我找到了引用的文章,来自DDJ:最大矩形问题

Answer 3

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

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

直觉

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

• 通过向上迭代直到达到填充区域来查找矩形的最大高度

• 通过左右向外迭代来找到矩形的最大宽度，直到高度不能容纳矩形的最大高度

例如，找到由黄点定义的矩形：

我们知道最大矩形必须是以这种方式构造的矩形之一（最大矩形必须在其底部有一个点，其中下一个填充的正方形的高度高于该点）。

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

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

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

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

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

使用动态规划，我们可以使用前一行中每个点的 、 、 和 来在线性时间内计算下一h行中每个点的、 、 和 。lrhlr

算法

给定 row ，我们通过定义三个数组- 、和matrix[i]来跟踪行中每个点的、 和。hlrheightleftright

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_right[j], cur_right)

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

执行

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