Maximal Rectangle

Maximal Rectangle

 

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

Naive Way: brute force的方法，对每一个点都遍历O(n^2)求出最大的长方形，算法复杂度是O(n^3)。由于有了Largest Rectangle in Histogram 的解法是O(n)，可以把矩阵从上到下扫一遍，得到n组Histogram的数据，每一组用上面的方法算最大rectangle，就可以实现O(n^2)的算法复杂度。

 

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int max = 0;
        if(matrix.length==0){return max;}
        int height[] = new int[matrix[0].length];
        for(int i = 0;i < matrix.length;i++){
            for(int j = 0;j < matrix[i].length;j++){
                int t = height[j]==0?0:height[j]-1;
                while(i+t < matrix.length && matrix[i+t][j]=='1') t++;
                height[j] = t;
            }
            max = Math.max(max,largestRectangleArea(height));
        }
        return max;
    }
    
    public int largestRectangleArea(int[] height) {
        int largest = 0;
        int i;
        Stack<Integer> stack = new Stack<Integer>();
        // forward
        i = 0;
        while(i < height.length){
            if(!stack.isEmpty() && height[i] < height[stack.peek()])
                largest = Math.max(largest, height[stack.pop()]*(i-(stack.isEmpty()?-1:stack.peek())-1));
            else
                stack.push(i++);
        }
        // backward
        while(!stack.isEmpty()){
            largest = Math.max(largest, height[stack.pop()] * (i-(stack.isEmpty()?-1:stack.peek())-1));
        }
        return largest;
    }
}

 

 

Improved Way: 这样做法算是比较普遍的做法。在Discuss里还有一种DP的做法，也是O(n^2)，颇受好评。https://oj.leetcode.com/discuss/20240/share-my-dp-solution

 

基本逻辑为：

left[i][j] // the left most position with '1' in row i connected with position[i][j]

right[i][j] // the right most position with '1' in row i connected with position[i][j] 

height[i][j] // current height in column j for position[i][j]

 

left[i][j] = matrix[i][j] =='1'? max(leftMostZeroPosition, left[i-1][j]): 0;

right[i][j] = matrix[i][j] =='1'?min(rightMostZeroPosition, right[i-1][j]):0;

height[i][j] = matrix[i][j] =='1'?height[i-1][j]+1:0;

area[i][j] = height[i][j] *( right[i][j] - left[i][j]);

所有2D array都可以用1D array表示。

 

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int max = 0;
        int n = matrix.length;
        if(n==0){return max;}
        int m = matrix[0].length;
        int h[] = new int[m];
        int l[] = new int[m];
        int r[] = new int[m];
        Arrays.fill(r, m);
        for(int i = 0;i < n;i++){
            int curLeft = 0, curRight = m;
            for(int j = 0;j < m;j++){
                l[j] = matrix[i][j]=='1'?Math.max(curLeft,l[j]):0;
                curLeft = matrix[i][j]=='1'?curLeft:j+1;
                
                r[m-1-j] = matrix[i][m-1-j]=='1'?Math.min(curRight,r[m-1-j]):m;
                curRight = matrix[i][m-1-j]=='1'?curRight:m-1-j;
                
                h[j] = matrix[i][j] =='1'?h[j]+1:0;
            }
            
            for(int j = 0;j < m;j++)
                max = Math.max(max, h[j] * (r[j]-l[j]));
        }
        return max;
    }
}

 

Math.max(curLeft,l[j]) 这一个逻辑使得当前最右边为1的位置与上一层保持一致性。

 

在GeeksforGeeks上有一个更容易懂的DP的做法，不过是正方形的。