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

public class Solution {
    class Bar{
        int height;
        int index;
        public Bar(int height, int index){this.height = height; this.index = index;}
    };
    
    public int largestRectangleArea(char[][] matrix, int[][] height, int line) {
        int totalWid = height[line].length;
        
        Stack<Bar> stack = new Stack<Bar>();
        int maxArea = 0;
        Bar left = null;
        
        for(int i=0; i<totalWid; i++){
            if(matrix[line][i] == '1'){
                if(line > 0){
                    height[line][i] = height[line-1][i] + 1;
                }else{
                    height[line][i] = 1;
                }
            }else{
                height[line][i] = 0;
            }
            
            if(stack.isEmpty() || height[line][i] > stack.peek().height){
                stack.push(new Bar(height[line][i], i));
            }else{
                int last = i;
                while(!stack.isEmpty() && stack.peek().height > height[line][i]){
                    left = stack.peek();
                    last = left.index;
                    stack.pop();
                    maxArea = Math.max((i - left.index) * left.height, maxArea);
                }
                stack.push(new Bar(height[line][i], last));
            }
        }
        while(!stack.isEmpty()){
            left = stack.peek();
            stack.pop();
            maxArea = Math.max((totalWid-left.index) * left.height, maxArea);
        }
        
        return maxArea;
    }
    
    
    public int maximalRectangle(char[][] matrix) {
        int rows = matrix.length;
        if(rows == 0)
            return 0;
        int cols = matrix[0].length;

        int maxArea = 0;
        int height[][] = new int[rows][cols];

        for(int i = 0; i < rows; i++){
            maxArea = Math.max(maxArea, largestRectangleArea(matrix, height, i));
        }
        return maxArea;
    }
}