85. 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.

For example, given the following matrix:

1
2
3
4
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.

解法1：

这题是运用了Largest Rectangle Area那题的解法。因为这题可以看成是一行一行的数字叠加起来，组成了一个histogram，求最大的面积。
那么实际的算法就是对于每一层，计算一个当前累积的histogram，然后再求一个最大面积就可以了。
C++

1

Java

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
public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        int res = 0;
        int[] heights = new int[matrix[0].length + 1];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                heights[j] = matrix[i][j] - '0' == 0 ? 0 : heights[j] + 1;
            }
            // calculate the maximum rectangle in histogram
            Stack<Integer> stack = new Stack<Integer>();
            for (int j = 0; j < heights.length; j++) {
                int height = heights[j];
                while (!stack.empty() && height < heights[stack.peek()]) {
                    int last = heights[stack.pop()];
                    int width = stack.empty() ? j : j - stack.peek() - 1;
                    res = Math.max(res, last * width);
                }
                stack.push(j);
            }
        }
        return res;
    }
}