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

Have you met this question in a real interview?

Yes

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.

思想：可以看成是largest rectangle in histogram的延展。只是这题是2D，每一行来计算largets rectangle in histogram

可以用一个数组记录到height[i]，代表至第i行的高度

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

        int[] height = new int[matrix[0].length];
        for (int i = 0; i < matrix.length; i++){
            ans = Math.max(ans, getLevelMax(i, matrix, height));
        }
        return ans;
    }

    private int getLevelMax(int level, boolean[][] matrix, int[] height) {

        Stack<Integer> stack = new Stack<Integer>();
        int ans = 0;
        for (int i = 0; i <= matrix[level].length; i++) {
            int heightCur = -1;

            if (i != matrix[level].length && matrix[level][i]) {
                heightCur = height[i] + 1;
                height[i] = heightCur;
            } else if (i != matrix[level].length && !matrix[level][i]) {
                heightCur = 0;
                height[i] = 0;
            }

            while (!stack.isEmpty() && heightCur <= height[stack.peek()]) {
                int prev = stack.pop();
                int width = i;
                if (!stack.isEmpty()) {
                    width = i - stack.peek() - 1;
                }

                ans = Math.max(ans, height[prev] * width);
            }
            stack.push(i);
        }
        return ans;
    }
}