class Solution {
    // 把当前元素作为矩阵的右下角，用一个数组记录当前行到当前位置的连续的1的个数，得到矩阵的最大宽
    // 垂直遍历，计算宽和高，得到面积，求出对应位置面积的最大值
    public int maximalRectangle(char[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int maxArea = 0;
        int[][] maxWidth = new int[row][col]; // 记录以当前元素为右下角的最大宽
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == '1') {
                    maxWidth[i][j] = (j > 0) ? maxWidth[i][j - 1] + 1 : 1;
                }
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == '1') {
                    int width = maxWidth[i][j];
                    int area = width;
                    for (int k = i - 1; k >= 0; k--) {
                        width = Math.min(maxWidth[k][j], width); //构建矩形的最大宽
                        area = Math.max(width*(i - k + 1), area);
                    }
                    maxArea = Math.max(area, maxArea);
                }
            }
        }
        return maxArea;
    }
}