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.

Largest Rectangle in Histogram 升级版。对于矩阵每行，可以看成是这个问题。height array对于相邻的行，假如当前的matrix[i][j] = 0，则无视上一行且当前height[j] = 0，如果matrix[i][j] = 1，则加上之前的height[j] += 1。

public class Solution {
    //Time: O(m*n)  Space: O(n)
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        
        int max = 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++) {
                height[j] = matrix[i][j] == '0' ? 0 : height[j] + 1;
            }
            int cur = largestRectangleArea(height);
            max = Math.max(max, cur);
        }
        return max;
    }
    
    public int largestRectangleArea(int[] height) {
        int max = 0;
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i <= height.length; i++) {
            int h = i == height.length ? -1 : height[i];
            while (!stack.isEmpty() && h < height[stack.peek()]) {
                int index = stack.pop();
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                max = Math.max(max, w * height[index]);
            }
            stack.push(i);
        }
        return max;
    }
}