Maximal Rectangle

Now this problem really follows the Largest Rectangle in Histogram.

Let's look at the reason.

In this small example, we can assume each row as a histogram with each bar at the corresponding height. Then we calculate the maximum of all these maximum rectangles, then, problem solved! 

public class MaxRectangle {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0)
            return 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] height = new int[m][n];
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (matrix[i][j] == '0')
                    height[i][j] = 0;
                else
                {
                    height[i][j] = (i == 0) ? 1 : height[i - 1][j] + 1;
                }
            }
        }
        int maxArea = 0;
        for (int i = 0; i < m; i++)
            maxArea = Math.max(maxArea, getArea(height[i]));
    
        return maxArea;
        
    }
    private int getArea(int[] height)
    {
        Stack stack = new Stack();
        int maxArea = 0;
        for (int i = 0; i <= height.length; i++)
        {
            int curr = (i == height.length) ? -1 : height[i];
            while (!stack.isEmpty() && curr <= height[stack.peek()])
            {
                int h = height[stack.pop()];
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, h * w);
            }
            stack.push(i);
        }
        return maxArea;
    }
}