最大矩形

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-rectangle

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例:

输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6

动态规划解法：

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length == 0)
            return 0;
        int maxArea = 0;
        int[][] horizontal = new int[matrix.length][matrix[0].length];
        int[][] vertical = new int[matrix.length][matrix[0].length];
        int[][] skew = new int[matrix.length][matrix[0].length];
        //初始化横向面积
        initHor(matrix, horizontal);
        //初始化纵向面积
        initVert(matrix, vertical);
        //计算斜向面积，并随时记录最大面积
        //初始化最左侧
        for (int i = 0; i < matrix.length; i++) {
            skew[i][0] = matrix[i][0] == '0' ? 0 : 1;
            maxArea = Math.max(Math.max(vertical[i][0], horizontal[i][0]), maxArea);
        }
        //初始化最上侧
        for (int i = 0; i < matrix[0].length; i++) {
            skew[0][i] = matrix[0][i] == '0' ? 0 : 1;
            maxArea = Math.max(Math.max(vertical[0][i], horizontal[0][i]), maxArea);
        }
        //计算其余各点的面积
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                char c = matrix[i][j];
                if (c != '0') {
                    //左上角、左边和上边都不为0，就需要计算面积，否则就填1
                    if (skew[i - 1][j] > 0 && skew[i][j - 1] > 0 && skew[i - 1][j - 1] > 0) {
                        //先确定高度
                        int height = vertical[i][j];
                        //再在这个高度范围内找到最小的宽度，并且以这个宽度计算面积
                        int minWidth = Integer.MAX_VALUE;

                        int tmp = 0;
                        int tmpMaxArea = 0;
                        while(tmp < height){
                            minWidth = Math.min(horizontal[i-tmp][j], minWidth);
                            tmpMaxArea = Math.max(tmpMaxArea,minWidth*(tmp+1));
                            tmp++;
                        }
                        skew[i][j] = tmpMaxArea;
                        maxArea = Math.max(tmpMaxArea, Math.max(Math.max(vertical[i][j], horizontal[i][j]), maxArea));
                    } else {
                        skew[i][j] = 1;
                        maxArea = Math.max(Math.max(vertical[i][j], horizontal[i][j]), maxArea);
                    }
                }
            }
        }
        return maxArea;
    }



    private void initVert(char[][] matrix, int[][] vertical) {
        //初始化最左边和最上边
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                char c = matrix[i][j];
                if (c != '0') {
                    if (i == 0) {
                        vertical[i][j] = 1;
                    } else {
                        vertical[i][j] = vertical[i - 1][j] + 1;
                    }
                }
            }
        }
    }

    private void initHor(char[][] matrix, int[][] horizontal) {
        //初始化最左边和最上边
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                char c = matrix[i][j];
                if (c != '0') {
                    if (j == 0) {
                        horizontal[i][j] = 1;
                    } else {
                        horizontal[i][j] = horizontal[i][j - 1] + 1;
                    }
                }
            }
        }
    }
}