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 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.

##Approach 1: Dynamic Programming The DP solution proceeds row by row, starting from the first row. Let the maximal rectangle area at row i and column j be computed by [right(i,j) - left(i,j)]*height(i,j).

All the 3 variables left, right, and height can be determined by the information from previous row, and also information from the current row. So it can be regarded as a DP solution. The transition equations are:

left(i,j) = max(left(i-1,j), cur_left), if matrix[i][j]=='1'; //cur_left can be determined from the current row
left(i,j) = 0, if matrix[i][j]=='0'
right(i,j) = min(right(i-1,j), cur_right), if matrix[i][j]=='1'; //cur_right can be determined from the current row
right(i,j) = n, if matrix[i][j]=='0'
height(i,j) = height(i-1,j) + 1, if matrix[i][j]=='1';
height(i,j) = 0, if matrix[i][j]=='0'

注意在matrix[i][j]=='0'时，将left(i,j）置为0，right(i,j)置为n，这样不会影响下一行的左右边界。 由于可以row by row来计算，因此left, right, height都可以采用长度为n的一维数组。

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int[] left = new int[n];
        int[] right = new int[n];
        int[] height = new int[n];
        Arrays.fill(left, 0);
        Arrays.fill(right, n);
        Arrays.fill(height, 0);
        int res = 0;
        for(int i = 0; i < m; i++) {
            int curLeft = 0, curRight = n;
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] == '1') {
                    height[j]++;
                    left[j] = Math.max(left[j], curLeft);
                } else {
                    height[j] = 0;
                    left[j] = 0;
                    curLeft = j+1;
                }
            }
            for(int j = n-1; j >= 0; j--) {
                if(matrix[i][j] == '1') {
                    right[j] = Math.min(right[j], curRight);
                } else {
                    right[j] = n;
                    curRight = j;
                }
            }
            for(int j = 0; j < n; j++) {
                res = Math.max(res, (right[j] - left[j]) * height[j]);
            }
        }
        return res;
    }
}

##Approach 2 解题思路为row by row，每一行时都可以看成是一个"84. Largest Rectangle"问题，只需维护一个heights数组即可。

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int[] heights = new int[n+1];
        heights[n] = 0;
        int maxArea = 0;
        for(int i = 0; i < m; i++) {
            Stack<Integer> stack = new Stack<>();
            for(int j = 0; j <= n; j++) {
                if(j < n) {
                    if(matrix[i][j] == '1') {
                        heights[j]++;
                    } else {
                        heights[j] = 0;
                    }
                }
                while(!stack.isEmpty() && heights[j] < heights[stack.peek()]) {
                    int h = heights[stack.pop()];
                    int w = stack.isEmpty() ? j : j - stack.peek() - 1;
                    maxArea = Math.max(maxArea, h * w);
                }
                stack.push(j);
            }
        }
        return maxArea;
    }
}