Maximal Rectangle 510

Question

Given a 2D boolean matrix filled with False and True, find the largest rectangle containing all True and return its area.

Example

Given a matrix:

[ [1, 1, 0, 0, 1],

[0, 1, 0, 0, 1],

[0, 0, 1, 1, 1],

[0, 0, 1, 1, 1],

[0, 0, 0, 0, 1] ]

return 6.

Solution

方法一：这道题是Largest Rectangle in Histogram直方图中最大的矩形问题的扩展，matrix有几行就有几个直方图。首先我们要构建“直方图”。

1) 第一行中，matrix值为0则相应直方图高度为0，matrix值为1则相应直方图高度为1

2) 从第二行开始，若matrix值为0则相应直方图高度为0，若matrix值为1则相应直方图高度为上一行直方图在该点的高度＋1

直方图构建完成后，则只需要逐行调用Largest Rectangle in Histogram直方图中最大的矩形问题的函数并找出最大值即可。

将代码写在一个函数中可以更简洁。

方法二：这道题还能用DP来解。对于某个点(i,j)，以该点为底边上的一点，以这个点向上能到达的高度的最大值为高，以在这条高度轴线上每一行向左右两边展开能到达的距离的最小值为宽的矩形为该点能取的矩形的最大值（好像并不是最大值，但一定会有一个点能取到最大的矩形）。用height[i][j]来记录（i， j）这个点向上能取的最大高度，用left[i][j]来记录(i, j)能取的最左边的左边界，用right[i][j]来记录（i，j）能取的最右边的右边界。因为当前点的各个值都只和上一行的点有关，因此要多建一行来初始化，同时可以用滚动数组来优化空间。

初始化：

height[0][j]=0 第一行所有点都为0
left[i][j]=0 假设每一个点的初始左边界都为0
right[i][j]=matrix[0].length - 1 假设每一个点的初始右边界都为matrix[0].length - 1

状态函数： 从左至右扫描更新当前行的height和left

如果matrix[i-1][j]==1 (i-1是因为多建了一行便于计算)
height[i][j] = height[i-1][j]+1
left[i][j] = max(left[i-1][j], curtLeft) curtLeft为当前行的左边界，每一行的左边界都是从0开始，直到遇到一个0，左边界就更新为j+1

如果matrix[i-1][j]==0
height[i][j] = 0
left[i][j] = 0
curtLeft = j + 1 更新左边界

从右到左扫描更新当前行的right

如果matrix[i-1][j]==1
right[i][j]=min(right[i-1][j], curtRight) curtRight为当前行的右边界，每一行的右边界都是从matrix[0].length - 1开始，直到遇到一个0，右边界就更新为j-1

如果matrix[i-1][j]==0
right[i][j] = matrix[0].length - 1
curtRight = j - 1 更新右边界

最后，再次扫描当前行每一个点，通过

height[i][j] * (right[i][j] - left[i][j] + 1)

来计算矩形面积，如果大于max，就更新。

可以用滚动数组来优化空间。

Reference

代码如下：

public class Solution {
    /**
     * @param matrix a boolean 2D matrix
     * @return an integer
     */
    public int maximalRectangle(boolean[][] matrix) {
        // Write your code here
        if(matrix == null || matrix.length == 0 || matrix[0].length ==0){
            return 0;
        }

        int n = matrix.length;
        int m = matrix[0].length;
        int[][] height = new int[n][m];

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(i == 0){
                    height[i][j] = (matrix[i][j] == false)? 0 : 1;
                }else{
                    height[i][j] = (matrix[i][j] == false)? 0 : (height[i - 1][j] + 1);
                }
            }
        }

        int max = 0;
        for(int i = 0; i < n; i++){
            max = Math.max(max, largestRectangleArea(height[i]));
        }

        return max;
    }

    private int largestRectangleArea(int[] heights){
        Stack<Integer> stack = new Stack<Integer>();
        int area = 0;
        for(int i = 0; i < heights.length; i++){
            while(!stack.isEmpty() && heights[i] < heights[stack.peek()]){
                int pos = stack.pop();
                int w = stack.isEmpty()? i : i - stack.peek() - 1;
                int h = heights[pos];
                area = Math.max(area, w * h);
            }
            stack.push(i);
        }

        while(!stack.isEmpty()){
            int pos = stack.pop();
            int w = stack.isEmpty()? heights.length : heights.length - stack.peek() - 1;
            int h = heights[pos];
            area = Math.max(area, w * h);
        }

        return area;
    }
}

Revised Version:

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length < 1) return 0;
        int n = matrix.length;
        if (n == 0) return 0;
        int m = matrix[0].length;
        if (m == 0) return 0;
        int[][] height = new int[n][m];

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (i == 0)
                    height[i][j] = ((matrix[i][j] == '1') ? 1 : 0);
                else
                    height[i][j] += ((matrix[i][j] == '1') ? height[i-1][j] + 1 : 0);
            }
        }

        int answer = 0;
        for (int i = 0; i < n; ++i) {
            Stack<Integer> S = new Stack<Integer>();  
            for (int j = 0; j < m; j++) {
                while (!S.empty() && height[i][j] < height[i][S.peek()]) {
                    int pos = S.peek();
                    S.pop();
                    answer = Math.max(answer, height[i][pos]*(S.empty()? j : j-S.peek()-1));
                }
                S.push(j);
            }
            while (!S.empty()) {
                int pos = S.peek();
                S.pop();
                answer = Math.max(answer, height[i][pos]*(S.empty()? m : m-S.peek()-1));
            }
        }
        return answer;
    }
}

DP:

    public int maximalRectangle(boolean[][] matrix) {
        //Write your code here
        if(matrix == null || matrix.length == 0 || matrix[0].length ==0){
            return 0;
        }

        int n = matrix.length;
        int m = matrix[0].length;
        int[] height = new int[m];
        int[] left = new int[m];
        int[] right = new int[m];
        Arrays.fill(right, m - 1);

        int max = 0;
        for(int i = 0; i < n; i++){
            int curtLeft = 0;
            int curtRight = m - 1;

            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == true) {
                    height[j]++;
                    left[j] = Math.max(left[j], curtLeft);
                } else {
                    height[j] = 0;
                    left[j] = 0; 
                    curtLeft = j + 1;
                }
            }

            for(int j = m - 1; j >= 0; j--){
                if(matrix[i][j] == true){
                    right[j] = Math.min(right[j], curtRight);
                }else{
                    right[j] = m;
                    curtRight = j - 1;
                }
            }

            for(int j = 0; j < m; j++){
                int area = (right[j] - left[j] + 1) * height[j];
                max = Math.max(max, area);
            }
        }

        return max;
    }