Description

LeetCode 85

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

Analysis

When firstly considering about this problem, the problem seems to be a extension of Largest Rectangle in Histogram. But how can we connect them?

Actually, Largest Rectangle in Histogram is a product that is from this problem and a border. In Largest Rectangle in Histogram, “1”s are continuous from the border. From the border to the up direction, if we get one “0”, then we get “1” again. So the problem can be efficiently solved in \(O(n)\) time. However, in this problem, “1”s may be not continuous. So we can’t just set the border be the bottom of the matrix. Conversely, each row may be the potential border. Therefore, what we should do is implement Largest Rectangle in Histogram to every conditions. One condition is setting one row as the border in the problem Largest Rectangle in Histogram.

How can we initialize the histogram for each row? We could count the maximum continuous “1”s. When we meet “1”, add one to the past row. When we meet “0”, set zero to this row.

Set the row size is \(m\) and the column size is \(n\). Then the time is \(O(m*n)\) and the space is \(O(n)\). If m is much smaller than n, then we could transpose the matrix. So we can also say the space is\(O(min(m,n))\).

Solution

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length==0||matrix[0].length==0) return 0;
        int res=0;
        int[] dp=new int[matrix[0].length];
        for(int j=0;j<matrix[0].length;j++)
        {
            dp[j]=matrix[0][j]-'0';
        }
        res=Math.max(res,largestRectangleArea(dp));
        for(int i=1;i<matrix.length;i++)
        {
            for(int j=0;j<matrix[0].length;j++)
            {
                if(matrix[i][j]=='1')
                    dp[j]=dp[j]+1;
                else dp[j]=0;
            }
            res=Math.max(res,largestRectangleArea(dp));
        }
        return res;
    }
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> s=new Stack<>();
        int res=0;
        int temp,tempi,start;
        for(int i=0;i<=heights.length;i++)
        {
            if(i==heights.length)
                temp=0;
            else
                temp=heights[i];
            while(s.size()!=0&&temp<heights[s.peek()])
            {
                tempi=s.pop();
                start=s.size()==0?-1:s.peek();
                res=Math.max(res,heights[tempi]*(i-start-1));
            }
            s.push(i);
        }
        return res;
    }
}

Reference

[1] https://www.youtube.com/watch?v=g8bSdXCG-lA

[2] http://ningziwen.com/2018/09/01/largest-rectangle-in-histogram/

Leave a Reply

Your email address will not be published. Required fields are marked *