题目链接

LeetCode

题目描述

给定一个仅包含 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
• 0 <= row, cols <= 200
• matrix[i][j] 为 '0' 或 '1'

  方法一：暴力法

  遍历每个点，求以这个点为矩阵右下角的所有矩阵面积。如下图的两个例子，橙色是当前遍历的点，然后虚线框圈出的矩阵是其中一个矩阵。
  
  怎么找出这样的矩阵呢？如下图，如果我们知道了以这个点结尾的连续 1 的个数的话，问题就变得简单了。
  

1. 首先求出高度是 1 的矩形面积，也就是它自身的数，如图中橙色的 4，面积就是 4。
2. 然后向上扩展一行，高度增加一，选出当前列最小的数字，作为矩阵的宽，求出面积，对应上图的矩形框。
3. 然后继续向上扩展，重复步骤 2。

按照上边的方法，遍历所有的点，求出所有的矩阵就可以了。
以橙色的点为右下角，高度为 1。

高度为 2。

高度为 3。

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length == 0){
            return 0;
        }
        int rows = matrix.length;
        int cols = matrix[0].length;
        // 动态保存当前列位置的连续 1 的个数
        int[][] width = new int[rows][cols];
        int minWidth;
        int ans = 0;
        for(int i = 0; i < rows; ++i){
            for(int j = 0; j < cols; ++j){
               if(matrix[i][j] == '1'){
                   if(j == 0){
                       width[i][j] = 1;
                   }else{
                       width[i][j] = width[i][j-1] + 1;
                   }
               }else{
                   width[i][j] = 0;
               }
               // 记录所有行中最小的数
               minWidth = width[i][j];
               for(int k = i; k >=0 && width[k][j] > 0; --k){
                   minWidth = Math.min(minWidth, width[k][j]);
                   // 更新最大面积
                   ans = Math.max(minWidth*(i - k + 1), ans);
               } 
            }
        }
        return ans;
    }
}

• 时间复杂度 O(m^2n)

• 空间复杂度 O(mn)

  方法二：单调栈 + 动态规划

  我们可以使用「84. 柱状图中最大的矩形的官方题解」中的单调栈的做法，将其应用在我们生成的柱状图中。
  对于每一列，进行遍历，利用单调栈记录大于等于当前位置宽度的上下位置（也就相当于高）。遍历每一列的矩形最大值。

  class Solution {
    public int maximalRectangle(char[][] matrix) {
        int row = matrix.length;
        if(row == 0){
            return 0;
        }
        int col = matrix[0].length;
        int[][] left = new int[row][col];
        // 记录每个位置的宽
        for(int i = 0; i < row; ++i){
            for(int j = 0; j < col; ++j){
                if(matrix[i][j] == '1'){
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }else{
                    left[i][j] = 0;
                }
            }
        }
        int res = 0;
        // 对于每一列
        // 遍历到 j 列说明前 j - 1列都已经得出结果
        for(int j = 0; j < col; ++j){
            // 上方第一个小于当前i行j列坐标值的下标
            int[] up = new int[row];
            // 下方第一个小于当前i行j列坐标值的下标
            int[] down = new int[row];
            // 设置栈， 单调递增栈
            Deque<Integer> stack = new LinkedList<Integer>();
            // 当前列，从上向下遍历，获取上方宽度小于当前位置值的第一个位置
            for(int i = 0; i < row; ++i){
                // 大于等于当前值位置的下标都出栈
                while(!stack.isEmpty() && left[stack.peekFirst()][j] >= left[i][j]){
                    stack.poll();
                }
                // 记录上方宽度小于当前位置值的第一个位置
                up[i] = stack.isEmpty() ? -1 : stack.peek();
                // 入栈当前下标
                stack.push(i);
            }
            // 清除栈
            stack.clear();
            // 当前列，从下向上遍历，获取下方宽度小于当前位置值的第一个位置
            for(int i = row - 1; i >= 0; --i){
                // 大于等于当前值位置的下标都出栈
                while(!stack.isEmpty() && left[stack.peekFirst()][j] >= left[i][j]){
                    stack.poll();
                }
                // 记录下方宽度小于当前位置值的第一个位置
                down[i] = stack.isEmpty() ? row : stack.peek();
                // 入栈当前下标
                stack.push(i);
            }
            // 计算每个位置的最大矩阵面积
            for(int i = 0; i < row; ++i){
                // down[i] - up[i] - 1 为宽度为 left[i][j] 的高
                res = Math.max(res, left[i][j] * (down[i] - up[i] - 1));
            }
        }
        return res;
    }
  }

• 时间复杂度 O(mn)

• 空间复杂度 O(mn)