📚 85. Maximal Rectangle

这道题值得hard的难度。
看了答案写出来的。值得多看几遍。

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], right[] = new int[n], height[] = new int[n];
        Arrays.fill(left,0); Arrays.fill(right,n); Arrays.fill(height,0);
        int max_area = 0;
        
        for(int i=0; i<m; i++) {
            int cur_left = 0, cur_right = n;
            // calculate height;
            for(int j=0; j<n; j++) {
                if(matrix[i][j]=='1')
                    height[j]++;
                else height[j] = 0;
            }
            // calculate left;
            for(int j=0; j<n; j++) {
                if(matrix[i][j]=='1')
                    left[j] = Math.max(left[j], cur_left);
                else {
                    left[j] = 0; // set back to "0",  to prepare for next iteration.
                    cur_left = j+1;
                }
            }
            // calculate right;
            for(int j=n-1; j>=0; j--) {
                if(matrix[i][j]=='1')
                    right[j] = Math.min(right[j], cur_right);
                else {
                    right[j] = n; // set back to "n",  to prepare for next iteration.
                    cur_right = j;
                }
            }
            // max_area;
            for(int j=0; j<n; j++){
                int new_area = (right[j] - left[j]) * height[j];
                max_area = Math.max(max_area, new_area);
            }
        }
        return max_area;
    }
}