原题链接

题目描述

给出一个只包含0和1的二维矩阵，找出最大的全部元素都是1的长方形区域，
返回该区域的面积。

示例

输入：
matrix = [
	["1","0","1","0","0"],
	["1","0","1","1","1"],
	["1","1","1","1","1"],
	["1","0","0","1","0"]
]
输出：6
解释：最大矩形如上图所示。

解析

每一层加上上面的层，将他们看作是柱状图。

第一层柱状图的高度["1","0","1","0","0"]，最大面积为1；

第二层及以上柱状图的高度["2","0","2","1","1"]，最大面积为3；

第三层及以上柱状图的高度["3","1","3","2","2"]，最大面积为6；

第四层及以上柱状图的高度["4","0","0","3","0"]，最大面积为4；

然后将题目转换成求直方图的最大面积

每遍历一层都有一个直方图

参考代码

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int col = matrix.length;
        int row = matrix[0].length;
        int[] heights = new int[row];
        int ans = 0;
        for (int i = 0; i < col; i++) {
            for (int j = 0; j < row; j++) {
                // 原数组是char类型的
                if (matrix[i][j] == '1') {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }
            }
            // 将每一行及上面的行，当作求解直方图的最大矩形面积
            ans = Math.max(ans, largestRectangleArea(heights));
        }
        return ans;
    }
    
    public int largestRectangleArea(int[] heights) {
        int area = 0, n = heights.length;
        // 遍历每个柱子，以当前柱子的高度作为矩形的高 h，
        // 从当前柱子向左右遍历，找到矩形的宽度 w。
        for (int i = 0; i < n; i++) {
            int w = 1, h = heights[i];
            if(h==0)
                continue;
            // 从i-1到heights[]左侧的边界
            int j= i - 1;
            // 如果有柱子比当前高度矮，则循环中断
            while (j >= 0 && heights[j] >= h) {
                w++;
                j--;
            }
            // 从i+1到height[]右侧的边界
            j = i + 1;
            // 如果有柱子比当前高度矮，则循环中断
            while (j < n && heights[j] >= h) {
                w++;
                j++;
            }
            area = Math.max(area, w * h);
        }
        return area;
    }   
}