leetcode(85)最大矩形

最大矩形

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