Maximal Rectangle

Given a 2Dbooleanmatrix filled withFalseandTrue, find the largest rectangle containing allTrueand return its area.

Example

Given a matrix:

[
  [1, 1, 0, 0, 1],
  [0, 1, 0, 0, 1],
  [0, 0, 1, 1, 1],
  [0, 0, 1, 1, 1],
  [0, 0, 0, 0, 1]
]

return6.

Solution: Build Histgram and maintain minitone stack.

public int maximalRectangle(boolean[][] matrix) {
    // Write your code here
    if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return 0;
    }
    int m = matrix.length, n = matrix[0].length;
    int[][] h = new int[m][n + 1];
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(!matrix[i][j]) {
                h[i][j] = 0;
            }
            else {
                if(i == 0) {
                    h[i][j] = 1;
                }
                else {
                    h[i][j] = h[i - 1][j] + 1;
                }
            }            
        }
    }
    int res = 0;
    Stack<Integer> stack = new Stack<Integer>();
    for(int i = 0; i < m; i++) {
        int idx = 0;
        int max = 0;
        while(idx < n + 1) {
            if(stack.isEmpty() || h[i][idx] > h[i][stack.peek()]) {
                stack.push(idx++);
            }
            else {
                int height = stack.pop();
                int len = stack.isEmpty() ? idx : idx - stack.peek() - 1;
                max = Math.max(max, len * h[i][height]);
            }
        }
        while(!stack.isEmpty()) {
            stack.pop();
        }
        res = Math.max(max, res);
    }
    return res;
}