Matrix Loop Solution - Maximal Rectangle - Analysis level + pre Process

Don't be afraid!

The idea below is to analyze the consistent Ones in the matrix, and define a matrix to save the values. After that, the problem is converted to be get the max area in an array, level by level … A second function is defined to calculate max area in an array, and a variable is used to retrieve the max value.

public class Solution {
        public int maximalRectangle(char[][] matrix) {
        if (matrix==null ||matrix.length==0){
            return 0;
        }
     
        int[][] heights=new int[matrix.length][matrix[0].length];
     
        // build heights table, once we have heights table, at each row, we can use
        // method which used in question of Largest Rectangle in Histogram to calculate
        // max area at until this row,.
     
        for (int row=0; row<matrix.length; row++){
            for (int col=0; col<matrix[0].length; col++){
                if (row==0){
                    heights[row][col]=matrix[row][col]=='0'?0:1;
                }
                else{
                    heights[row][col]=matrix[row][col]=='0'?0:heights[row-1][col]+1;
                }
            }
        }
     
        int max=0;
     
        for (int row=0; row<heights.length; row++){
          // update max with maxArea of each row
            max=Math.max(max, maxArea(heights[row]));
        }
     
        return max;
    }
    // calculate maxArea for each row
    private int maxArea(int[] heights){
        if (heights==null||heights.length==0){
            return 0;
        }
     
        Stack<Integer> stack=new Stack<Integer>();
        int max=0;
     
        int i=0;
        while(i<heights.length){
            if (stack.isEmpty()||heights[stack.peek()]<=heights[i]){
                stack.push(i);
                i++;
            }
            else{
                int height=heights[stack.pop()];
             
                int width=stack.isEmpty()?i:i-stack.peek()-1;
             
                max=Math.max(max, height*width);
            }
         
        }
        while(!stack.isEmpty()){
            int height=heights[stack.pop()];
         
            int width=stack.isEmpty()?i:i-stack.peek()-1;
            max=Math.max(max, height*width);
        }
     
        return max;
     
    }
}

http://rleetcode.blogspot.com/2014/01/maximal-rectangle-java.html