拼图：找到最大的矩形（最大的矩形问题）

Question

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

比方说，画面看起来像这样（ '＃' 代表填充区域）：

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

一个可能的解决方案是：

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

一般情况下我喜欢找出一个解决方案。虽然这次我想避免浪费时间在我自己身上摸索，因为这对我正在开发的项目有实际的用处。有没有一个众所周知的解决方案？

Shog9写道：

是您输入的阵列（如暗示的其他响应），或在任意大小，位置的矩形的形式闭塞的列表（如可能在的情况下处理窗口位置时的窗口系统）？

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

Answer 1

@lassevk

我发现引用的文章，从DDJ：The Maximal Rectangle Problem

Answer 2

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

您的特定问题在网页上开始有点偏下，搜索网页上的文字最大矩形问题。

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

Answer 3

@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）..这可能就是我会拿出。

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

Answer 4

我就是多布博士的文章的作者，并获得偶尔问起的实现。这里是一个简单的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] 

上面的实施当然是没有任何幻想，但它是非常接近的博士解释多布的文章，应该很容易翻译成任何需要的东西。

Answer 5

我在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 6

挣扎这么多，我已经写了这个算法...只要看到代码后...

你明白that.This代码说话！

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