1、前言

2、思路

这道题最有用也是最有意义的一种解法是：将此题转化为寻找柱状图中最大矩形的问题。怎么转换呢？

首先，我们遍历 matrix 的每一行，将每一行1的个数作为 height 的数组的值，也就是矩形的高度。那么问题就简单了，我们只需要遍历每一行，求 height 数组的值，然后将数组输入求最大矩形面积。到最后留下的最大的，也就是二维数组中的最大矩形。

3、代码

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || matrix.length == 0 ||matrix[0].length == 0){
            return 0;
        }

        int m = matrix.length, n = matrix[0].length;
        int[] heights = new int[n];
        int maxArea = 0;

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == '1'){
                    heights[j] += 1;
                }else {
                    heights[j] = 0;
                }
            }

            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }

        return maxArea;
    }

    private int largestRectangleArea(int[] heights){
        if(heights == null || heights.length == 0){
            return 0;
        }

        int m = heights.length;
        int[] leftMemo = new int[m];
        leftMemo[0] = -1;
        for (int i = 1; i < heights.length; i++) {
            int left = i - 1;
            while(left >= 0 && heights[left] >= heights[i]){
                left = leftMemo[left];
            }

            leftMemo[i] = left;
        }

        int[] rightMemo = new int[m];
        rightMemo[m - 1] = m;
        for (int i = m - 2; i >= 0; i--) {
            int right = i + 1;
            while(right < m && heights[right] >= heights[i]){
                right = rightMemo[right];
            }
            rightMemo[i] = right;
        }

        int max = 0;
        for (int i = 0; i < heights.length; i++) {
            max = Math.max(max, (rightMemo[i] - leftMemo[i] - 1) * heights[i]);
        }

        return max;
    }
}