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.
Solution: 
"假设把矩阵沿着某一行切下来，然后把切的行作为底面，将自底面往上的矩阵看成一个直方图。直方图的中每个项的高度就是从底面行开始往上1的数量。根据Largest Rectangle in Histogram我们就可以求出当前行作为矩阵下边缘的一个最大矩阵。接下来如果对每一行都做一次Largest Rectangle in Histogram，从其中选出最大的矩阵，那么它就是整个矩阵中面积最大的子矩阵。
然而在这里我们会发现一些动态规划的踪迹，如果我们知道上一行直方图的高度，我们只需要看新加进来的行（底面）上对应的列元素是不是0，如果是，则高度是0，否则则是上一行直方图的高度加1。"
Run time complexity is O(m * n), space complexity is O(n).
Reference: http://blog.csdn.net/linhuanmars/article/details/24444491

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        
        int[] height = new int[matrix[0].length];
        int maxArea = 0;
        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;
            }
            maxArea = Math.max(maxArea, largestArea(height));
        }
        
        return maxArea;
    }
    
    public int largestArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        
        int max = 0;
        Stack stack = new Stack();
        
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {
                int index = stack.pop();
                int curArea = stack.isEmpty() ? height[index] * i : height[index] * (i - stack.peek() - 1);
                max = Math.max(max, curArea);
            }
            stack.push(i);
        }
        
        while (!stack.isEmpty()) {
            int index = stack.pop();
            int curArea = stack.isEmpty() ? height[index] * height.length : height[index] * (height.length - stack.peek() - 1);
            max = Math.max(max, curArea);
        }
        
        return max;
    }
}