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.

Solution:

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix==null || matrix.length==0 || matrix[0].length==0) return 0;
        int [] l = new int [matrix[0].length];
        int [] r = new int [matrix[0].length];
        int [] h = new int [matrix[0].length];
        Arrays.fill(r,matrix[0].length);
        int ret = 0;
        for(int i = 0 ; i < matrix.length; i++){
            int cl =0 , cr = matrix[0].length;
            for(int j = 0 ; j < matrix[0].length ; j++){
                if(matrix[i][j]=='1') h[j] = h[j]+1;
                else h[j] = 0;
            }
            for(int j = 0 ; j < matrix[0].length ; j++){
                if(matrix[i][j]=='1') l[j] = Math.max(l[j],cl);
                else {
                    l[j]=0;
                    cl = j+1;
                }
            }
            for(int j = matrix[0].length-1 ; j>=0 ;j--){
                if(matrix[i][j]=='1') r[j] = Math.min(r[j],cr);
                else{
                    r[j] = matrix[0].length;
                    cr = j;
                }
            }
            for(int j = 0 ; j < matrix[0].length ; j++){
                ret= Math.max(ret,(r[j]-l[j])*h[j]);
            }
        }
        return ret;
    }
}

思路：

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int rows = matrix.length;
        if(rows == 0) return 0;
        int cols = matrix[0].length;
        int[][] r = new int[rows][cols];
        int[][] c = new int[rows][cols];
        int max = 0;
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                if(j == 0) {
                    r[i][j] = (matrix[i][j] == '1') ? 1 : 0;
                } else {
                    r[i][j] = (matrix[i][j] == '1') ? 1 + r[i][j - 1] : 0;
                }
                
                if(i == 0) {
                    c[i][j] = (matrix[i][j] == '1') ? 1 : 0;
                } else {
                    c[i][j] = (matrix[i][j] == '1') ? 1 + c[i - 1][j] : 0;
                }
            }
        }
        int minY = rows; 
        for(int j = 0; j < cols; j++) {
            for(int i = 0; i < rows; i++) {
                if(c[i][j] != 0) {
                    minY = r[i][j];
                    for(int k = 0; k < c[i][j]; k++) {
                        minY = (r[i - k][j] < minY) ? r[i - k][j] : minY;
                        int temp = (k + 1) * minY;
                        max = (temp > max) ? temp : max;
                    }
                }                
            }
        }
        return max;
    }
}