algorithm - 谜题：查找最大矩形（最大矩形问题）

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线性l时间内下一行中每个点的、和。rhlr

算法

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

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是我们遇到的最左边出现的填充空间。

执行

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

Answer 4

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

}

Answer 5

@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).. 这可能是我想出的。

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

Answer 6

用纯 Javascript 实现基于堆栈的算法（具有线性时间复杂度）：

function maxRectangle(mask) {
  var best = {area: 0}
  const width = mask[0].length
  const depth = Array(width).fill(0)
  for (var y = 0; y < mask.length; y++) {
    const ranges = Array()
    for (var x = 0; x < width; x++) {
      const d = depth[x] = mask[y][x] ? depth[x] + 1 : 0
      if (!ranges.length || ranges[ranges.length - 1].height < d) {
        ranges.push({left: x, height: d})
      } else {
        for (var j = ranges.length - 1; j >= 0 && ranges[j].height >= d; j--) {
          const {left, height} = ranges[j]
          const area = (x - left) * height
          if (area > best.area) {
            best = {area, left, top: y + 1 - height, right: x, bottom: y + 1}
          }
        }
        ranges.splice(j+2)
        ranges[j+1].height = d
      }
    }
  }
  return best;
}

var example = [
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0],
[0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0],
[0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]]

console.log(maxRectangle(example))