题目描述

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

样例

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

算法分析

单调栈

一共有n行，枚举每一行作为基准线，以该基准线为底线往上的图像形成一个柱状图(黄色区域)，用单调栈算出柱状图中最大的矩形（ LeetCode 84题的解题方法 ），再算出所有基准线情况的最大值res

状态表示

• h[i,j]表示所有以(i,j)为终点，能往上延伸的最大高度。

状态计算

• 若当前位置是0，则h[i,j] = 0
• 若当前位置是1，则h[i,j] = 1 + h[i,j]

时间复杂度 $O(n^2)$

Java 代码

class Solution {
    public static int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] stk = new int[n + 10];
        int tt = 0;
        int[] left = new int[n + 10];
        for(int i = 0;i < n;i ++)
        {
            while(tt != 0 && heights[stk[tt]] >= heights[i]) tt --;
            if(tt == 0) left[i] = -1;
            else left[i] = stk[tt];
            stk[++ tt] = i;
        }

        tt = 0;
        int[] right = new int[n + 10];
        for(int i = n - 1;i >= 0;i --)
        {
            while(tt != 0 && heights[stk[tt]] >= heights[i]) tt --;
            if(tt == 0) right[i] = n;
            else right[i] = stk[tt];
            stk[++ tt] = i;
        }
        int ans = 0;
        for(int i = 0;i < n;i ++)
        {
            ans = Math.max(ans,(right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length <= 0 || matrix[0].length < 0) return 0;
        int n = matrix.length;
        int m = matrix[0].length;
        int[][] h = new int[n + 10][m + 10];

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

        int res = 0;
        for(int i = 0;i < n;i ++) res = Math.max(res,largestRectangleArea(h[i]));

        return res;
    }
}