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.

This is an extension of 84 Largest Rectangle in Histogram, you need to convert the 2D matrix, so that each row is a histogram of previous rows. if current row-col is '0', simple treat this row-col in histogram as 0.

Non-Related Issue: 221 Maximal Square

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int[][] data = new int[matrix.length][matrix[0].length];
        for(int i=0; i< matrix[0].length; i++){
            data[0][i] = matrix[0][i] == '0' ? 0 :1;
        }

        for(int i=1; i< matrix.length; i++){
            for(int j=0; j < matrix[0].length; j++){
                if(matrix[i][j] != '0'){
                    data[i][j] += data[i-1][j] +  1;
                }else{
                    data[i][j] = 0;
                }
            }
        }
        int max = 0;
        for(int i=data.length-1; i>=0; i--){

            max = Math.max(max, maximalInHistogram(data[i]));
            if(max >= i * data[i].length) break;

        }
        return max;
    }

    private int maximalInHistogram(int[] data){
        Stack<Integer> stack = new Stack<>();

        int max = 0;
        int i = 0;
        while(i <= data.length){
            int val = i < data.length ? data[i] : 0;
            if(stack.empty() || val >= data[stack.peek()]){
                stack.push(i);
                i++;
            }else{
                int h = stack.pop();
                int w = stack.empty() ? i : i-stack.peek()-1;
                max = Math.max(max, data[h] * w);
            }
        }

        return max;
    }
}