Java solution for better understanding


  • 0
    B

    public class Solution {
    public static int maximalRectangle(char[][] matrix){
    if(matrix == null||matrix.length==0||matrix[0].length==0){
    return 0;
    }
    int matrixcl = matrix[0].length; //numbers of columns
    int matrixrw = matrix.length; //numbers of rows
    int[][] hist = transfertohistogram(matrix);
    int maxarea = 0;
    for(int r = 0;r<matrixrw;r++){
    maxarea = Math.max(maxarea, largestrectangle(hist[r]));
    }
    return maxarea;
    }
    private static int[][] transfertohistogram(char[][] charmatrix){
    int matrixcl = charmatrix[0].length;
    int matrixrw = charmatrix.length;
    int[][] histogram = new int[matrixrw][matrixcl];
    for(int r = 0; r<matrixrw; r++){
    for(int c = 0; c<matrixcl; c++){
    if(charmatrix[r][c]=='0'){histogram[r][c]=0;}
    else{
    histogram[r][c] = (r==0)? 1:histogram[r-1][c]+1;
    }
    }
    }
    return histogram;
    }
    private static int largestrectangle(int[] height){
    int maxArea = 0;
    Stack<Integer> s = new Stack<Integer>();
    int len = height.length;
    int i = 0;
    while(i<=len){
    int h = (i==len? 0:height[i]);
    if(s.isEmpty()||h>=height[s.peek()]){
    s.push(i);
    i++;
    }
    else{
    int tp = s.pop();
    maxArea = Math.max(maxArea, height[tp]*(s.isEmpty()? i: i-1-s.peek()));
    }
    }
    return maxArea;
    }
    }
    I think it is better to understand. Firstly, I change it to histogram question for each row and then we just need to take benefit from the histogram solution. The rest parts is find the maximum value for all rows.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.