原题

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

示例：

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

解法

思想

这道题可以分解成若干leetcode84-柱状图中最大的矩形的子问题，可以使用相同的方法。

我们从上往下动态规划二维数组，每增加一行就会出现不同的柱状区域。

从每一次得到的最大矩形面积中获取最大值，就是该题的答案

代码

class Solution {
    public int largestRectangleArea(int[] heights) {
        int length = heights.length;
        if(length==0) return 0;
        int max = 0;
        int left[] = new int[length];
        int right[] = new int[length];
        left[0] = -1;
        right[length-1] = length;
        for(int i = 1;i<length;i++){
            //如果左边一列比当前列矮，则left就等于左边一列的下标。
            if(heights[i]>heights[i-1]) left[i] = i-1;
            else{
                //否则沿着左边这列的left一直查找过去，直到找到比当前列低的一列
                left[i] =  left[i-1];
                while(left[i]!=-1&&heights[left[i]]>=heights[i])
                    left[i] = left[left[i]];
            }
        }
        for(int i = length-2;i>=0;i--){
            //如果右边一列比当前列矮，则right就等于右边一列的下标。
            if(heights[i]>heights[i+1]) right[i] = i+1;
            else{
                //否则沿着右边这列的right一直查找过去，直到找到比当前列低的一列
                right[i] =  right[i+1];
                while(right[i]!=length&&heights[right[i]]>=heights[i])
                    right[i] = right[right[i]];
            }
        }
        for(int i = 0;i<length;i++){
            int area = (right[i]-left[i]-1)*heights[i];
            if(area>max) max = area;
        }
        return max;
    }
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length == 0) return 0;
        int height[] = new int[matrix[0].length];
        int max = 0;
        for(char[] line:matrix){
            //每增加一行改变height数组
            for(int i=0;i<line.length;i++){
                if(line[i]=='0') height[i]=0;
                else height[i] += 1;
            }
            int area = largestRectangleArea(height);
            if(area>max) max=area;
        }
        return max;
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode85-%e6%9c%80%e5%a4%a7%e7%9f%a9%e5%bd%a2/

leetcode85-最大矩形

原题

解法

思想

代码

相关推荐

发表回复