LeetCode - 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.

 

Solution1:

时间复杂度：O(m*m*n)

 

public int maximalRectangle(char[][] matrix) {
    if(matrix.length==0 || matrix[0].length==0) return 0;
    int h = matrix.length, w = matrix[0].length;
    int[][] f = new int[h][w];
    f[0][0] = matrix[0][0] - '0';
    for(int i=0; i<h; i++) {
        f[i][0] = matrix[i][0] - '0';
        for(int j=1; j<w; j++) {
            f[i][j] = matrix[i][j]=='0' ? 0 : f[i][j-1]+1;
        }
    }
    int maxArea = 0;
    for(int i=0; i<h; i++) {
        for(int j=0; j<w; j++) {
            maxArea = Math.max(maxArea, maxSubRectangle(f, i, j));
        }
    }
    return maxArea;
}

private int maxSubRectangle(int[][] f, int m, int n) {
    int height = 0;
    int width = f[m][n];
    for(int i=m-1; i>=0; i--) {
        if(f[i][n]<width) break;
        height++;
    }
    for(int i=m; i<f.length; i++) {
        if(f[i][n]<width) break;
        height++;
    }
    return height * width;
}

 

 

Solution2:

时间复杂度：O(m*n)

 

public int maximalRectangle(char[][] matrix) {  
    if(matrix==null || matrix.length==0 || matrix[0].length==0) {  
        return 0;  
    }  
    int maxArea = 0;  
    int[] height = new int[matrix[0].length+1];  
    for(int i=0;i<matrix.length;i++) {  
        for(int j=0;j<matrix[0].length;j++) {  
            height[j] = matrix[i][j]=='0'?0:height[j]+1;  
        }  
        maxArea = Math.max(maxArea, largestRectangleArea(height));  
    }  
    return maxArea;  
}

private int largestRectangleArea(int[] h) {
    Stack<Integer> stack = new Stack<>();
    int maxArea = 0, i = 0;
    // int[] h = Arrays.copyOf(height, height.length+1);
    while(i<h.length) {
        if(stack.isEmpty() || h[i]>=h[stack.peek()]) {
            stack.push(i++);
        } else {
            int t = stack.pop();
            maxArea = Math.max(maxArea, h[t]*(stack.isEmpty()?i:(i-stack.peek()-1)));
        }
    }
    return maxArea;
}