Description

Maximal Rectangle

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

在给出的矩阵中，1表示元素，0表示空，找出最大矩形的面积。

Solution

本题可以利用《84. Largest Rectangle in Histogram》 的代码。

下面来看看如何转换成 84 题的直方图求解问题：

矩阵：
 [10100]
 [10111]
 [11111]
 [10010]

第一行，将 0 及其上方元素去掉：
 [1 1  ]

第二行，将 0 及其上方元素去掉：
 [1 1  ]
 [1 111]

第三行，将 0 及其上方元素去掉：
 [1 1  ]
 [1 111]
 [11111]

第四行，将 0 及其上方元素去掉：
 [1    ]
 [1  1 ]
 [1  1 ]
 [1  1 ]

通过四次转换，其实得到四个直方图：
[10100]、[20211]、[31322]、[4030]

至此已将矩阵问题转换成了之前的直方图问题。使用相应代码求解即可。

下面largestRectangleArea的代码点击这里查看。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func maximalRectangle(matrix [][]byte) int {
    h := len(matrix)
    if h == 0 {
        return h
    }
    w := len(matrix[0])

    max := 0
    heights := make([]int, w)
    for j := 0; j < h; j++ {
        for i := 0; i < w; i++ {
            if matrix[j][i] == '1' {
                heights[i]++
            } else {
                heights[i] = 0
            }
        }
        max = maxInt(max, largestRectangleArea(heights))
    }

    return max
}

Similar Problem