Description

Given a 2D booleanmatrix filled with Falseand True, find the largest rectangle containing all Trueand 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

对每一行的height做Largest Rectangle in Histogram

public class Solution {
    /*
     * @param matrix: a boolean 2D matrix
     * @return: an integer
     */
    public int maximalRectangle(boolean[][] matrix) {
        // write your code here
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }

        int n = matrix.length;
        int m = matrix[0].length;
        int max = 0;

        int[] heights = new int[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                heights[j] = matrix[i][j] ? heights[j] + 1 : 0;
            }

            max = Math.max(max, maximalRectangle(heights));
        }

        return max;
    }

    private int maximalRectangle(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }

        int max = 0;
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i <= heights.length; i++) {
            int curH = i == heights.length ? 0 : heights[i];
            while (!stack.isEmpty() && heights[stack.peek()] > curH) {
                int h = heights[stack.pop()];
                int leftIndex = stack.isEmpty() ? -1 : stack.peek();
                max = Math.max(max, h * (i - leftIndex - 1));
            }

            stack.push(i);
        }

        return max;
    }
}