一、题目要求

• 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
• 示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6

• 示例 2：

输入：matrix = []
输出：0

• 示例 3：

输入：matrix = [["0"]]
输出：0

• 示例 4：

输入：matrix = [["1"]]
输出：1

• 示例 5：

输入：matrix = [["0","0"]]
输出：0

• 提示：
• • rows == matrix.length；
• • cols == matrix[0].length；
• • 1 <= row, cols <= 200；
• • matrix[i][j] 为 ‘0’ 或 ‘1’。

二、求解算法

① 暴力破解

• 遍历每个点，求以这个点为矩阵右下角的所有矩阵面积。如下所示，橙色是当前遍历的点，然后虚线框圈出的矩阵是其中一个矩阵：

• 怎么找出这样的矩阵呢？如下所示，如果知道以这个点结尾的连续 1 的个数的话，问题就变得简单：

• 具体步骤：
• • A. 首先求出高度是 1 的矩形面积，也就是它自身的数，如上图中橙色的 4，面积就是 4。
• • B. 然后向上扩展一行，高度增加一，选出当前列最小的数字，作为矩阵的宽，求出面积，对应上图的矩形框。
• • C. 然后继续向上扩展，重复步骤 B。
• 按照上边的方法，遍历所有的点，求出所有的矩阵就可以。
• 以橙色的点为右下角：
• • 高度为 1：

• • 高度为 2：

• • 高度为 3：

• Java 示例：

public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0) {
        return 0;
    }
    // 保存以当前数字结尾的连续 1 的个数
    int[][] width = new int[matrix.length][matrix[0].length];
    int maxArea = 0;
    // 遍历每一行
    for (int row = 0; row < matrix.length; row++) {
        for (int col = 0; col < matrix[0].length; col++) {
            // 更新 width
            if (matrix[row][col] == '1') {
                if (col == 0) {
                    width[row][col] = 1;
                } else {
                    width[row][col] = width[row][col - 1] + 1;
                }
            } else {
                width[row][col] = 0;
            }
            // 记录所有行中最小的数
            int minWidth = width[row][col];
            // 向上扩展行
            for (int up_row = row; up_row >= 0; up_row--) {
                int height = row - up_row + 1;
                // 找最小的数作为矩阵的宽
                minWidth = Math.min(minWidth, width[up_row][col]);
                // 更新面积
                maxArea = Math.max(maxArea, height * minWidth);
            }
        }
    }
    return maxArea;
}

② 栈

• 要是阅读过 【数据结构与算法】之柱状图中最大矩形的求解思路和算法示例，再看下边的橙色的部分，是不是特别眼熟？

• 不难想到，求出每一层的 heights[] 然后传给上一题的函数就可以。
• Java 示例：

public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0) {
        return 0;
    }
    int[] heights = new int[matrix[0].length];
    int maxArea = 0;
    for (int row = 0; row < matrix.length; row++) {
        // 遍历每一列，更新高度
        for (int col = 0; col < matrix[0].length; col++) {
            if (matrix[row][col] == '1') {
                heights[col] += 1;
            } else {
                heights[col] = 0;
            }
        }
        // 更新函数
        maxArea = Math.max(maxArea, largestRectangleArea(heights));
    }
    return maxArea;
}

public int largestRectangleArea(int[] heights) {
    int maxArea = 0;
    Stack<Integer> stack = new Stack<>();
    int p = 0;
    while (p < heights.length) {
        // 栈空入栈
        if (stack.isEmpty()) {
            stack.push(p);
            p++;
        } else {
            int top = stack.peek();
            // 当前高度大于栈顶，入栈
            if (heights[p] >= heights[top]) {
                stack.push(p);
                p++;
            } else {
                // 保存栈顶高度
                int height = heights[stack.pop()];
                // 左边第一个小于当前柱子的下标
                int leftLessMin = stack.isEmpty() ? -1 : stack.peek();
                // 右边第一个小于当前柱子的下标
                int RightLessMin = p;
                // 计算面积
                int area = (RightLessMin - leftLessMin - 1) * height;
                maxArea = Math.max(area, maxArea);
            }
        }
    }
    while (!stack.isEmpty()) {
        // 保存栈顶高度
        int height = heights[stack.pop()];
        // 左边第一个小于当前柱子的下标
        int leftLessMin = stack.isEmpty() ? -1 : stack.peek();
        // 右边没有小于当前高度的柱子，所以赋值为数组的长度便于计算
        int RightLessMin = heights.length;
        int area = (RightLessMin - leftLessMin - 1) * height;
        maxArea = Math.max(area, maxArea);
    }
    return maxArea;
}

③ 动态规划

• 解法②中，更新一次 heights，就利用之前的算法，求一遍 leftLessMin [ ] 和 rightLessMin [ ]，然后更新面积。而其实，求 leftLessMin [ ] 和 rightLessMin [ ] 可以利用之前的 leftLessMin [ ] 和 rightLessMin [ ] 来更新本次的。
• 回想一下 leftLessMin [ ] 和 rightLessMin [ ] 的含义， leftLessMin [ i ] 代表左边第一个比当前柱子矮的下标，如下图橙色柱子时当前遍历的柱子，rightLessMin [ ] 时右边第一个：

• left 和 right 是对称关系，下边只考虑 left 的求法。如下图，如果当前新增的层全部是 1，当然这时最完美的情况，那么 leftLessMin [ ] 根本不需要改变：

• 然而事实是残酷的，一定会有 0 的出现：

• 考虑最后一个柱子的更新，上一层的 leftLessMin = 1，也就是蓝色 0 的位置是第一个比它低的柱子。但是在当前层，由于中间出现了 0。所以不再是之前的 leftLessMin ，而是和上次出现 0 的位置进行比较（因为 0 一定比当前柱子小），谁的下标大，更接近当前柱子，就选择谁。上图中出现 0 的位置是 2，之前的 leftLessMin 是 1，选一个较大的，那就是 2 了。
• Java 示例：

public int maximalRectangle4(char[][] matrix) {
    if (matrix.length == 0) {
        return 0;
    }
    int maxArea = 0;
    int cols = matrix[0].length;
    int[] leftLessMin = new int[cols];
    int[] rightLessMin = new int[cols];
    // 初始化为 -1，也就是最左边
    Arrays.fill(leftLessMin, -1); 
    // 初始化为 cols，也就是最右边
    Arrays.fill(rightLessMin, cols); 
    int[] heights = new int[cols];
    for (int row = 0; row < matrix.length; row++) {
        // 更新所有高度
        for (int col = 0; col < cols; col++) {
            if (matrix[row][col] == '1') {
                heights[col] += 1;
            } else {
                heights[col] = 0;
            }
        }
		// 更新所有leftLessMin
        int boundary = -1; // 记录上次出现 0 的位置
        for (int col = 0; col < cols; col++) {
            if (matrix[row][col] == '1') {
                // 和上次出现 0 的位置比较
                leftLessMin[col] = Math.max(leftLessMin[col], boundary);
            } else {
                // 当前是 0 代表当前高度是 0，所以初始化为 -1，防止对下次循环的影响
                leftLessMin[col] = -1; 
                // 更新 0 的位置
                boundary = col;
            }
        }
        // 右边同理
        boundary = cols;
        for (int col = cols - 1; col >= 0; col--) {
            if (matrix[row][col] == '1') {
                rightLessMin[col] = Math.min(rightLessMin[col], boundary);
            } else {
                rightLessMin[col] = cols;
                boundary = col;
            }
        }
		
        // 更新所有面积
        for (int col = cols - 1; col >= 0; col--) {
            int area = (rightLessMin[col] - leftLessMin[col] - 1) * heights[col];
            maxArea = Math.max(area, maxArea);
        }
    }
    return maxArea;
}