Maximal Rectangle(Hard)

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

这一题的核心算法其实和Largest Rectangle in Histogram一样， 对每一行都求出每个元素对应的高度， 这个高度就是对应的连续1的长度， 然后对每一行都更新一次最大矩形面积，那么这个问题就变成了Largest Rectangle in Histogram，用相同的方法求解就行了。总结来说就是对矩阵中的每一行，执行一遍Largest Rectangle in Histogram算法。

public int maximalRectangle(char[][] matrix) {
    if (matrix == null || matrix.length == 0)
            return 0;
    int largestRectangle = 0;
    int[] height = new int[matrix[0].length];
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            int h = matrix[i][j] - '0';
            height[j] = h == 0 ? 0 : height[j] + 1;
        }
        largestRectangle = Math.max(largestRectangle, largestRectangleArea(height));
    }
    return largestRectangle;
}