剑指 Offer II 040. 矩阵中最大的矩形

题目

给定一个由0 和 1组成的矩阵 matrix，找出只包含 1 的最大矩形，并返回其面积。

注意：此题 matrix输入格式为一维 01 字符串数组。

示例 1：
示例1
输入：matrix = [“10100”,”10111”,”11111”,”10010”]
输出：6
解释：最大矩形如上图所示。

示例 2：
输入：matrix = []
输出：0

示例 3：
输入：matrix = [“0”]
输出：0

示例 4：
输入：matrix = [“1”]
输出：1

示例 5：
输入：matrix = [“00”]
输出：0

提示：

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

注意：本题与主站85题相同（输入参数格式不同）

题解

public int maximalRectangle(String[] matrix) {
    int area = 0, rows = matrix.length;
    if (rows == 0) {
        return area;
    }

    int cols = matrix[0].length();
    // 最后一列补0 保证所有数字出栈
    int[][] dp = new int[rows][cols + 1];
    // 初始化垂直方向1的个数
    // 类似39题，倒叙求矩阵中柱子最大面积
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i].charAt(j) == '1') {
                dp[i][j] = (i == 0 ? 0 : dp[i - 1][j]) + 1;
            }
        }
    }

    Stack<Integer> stack = new Stack<>();
    for (int i = rows - 1; i >= 0; i--) {
        stack.push(-1);
        for (int j = 0; j < cols + 1; j++) {
            while (stack.size() > 1 && dp[i][stack.peek()] >= dp[i][j]) {
                area = Integer.max(area, dp[i][stack.pop()] * (j - stack.peek() - 1));
            }
            stack.push(j);
        }
        stack.clear();
    }

    return area;
}