AdSense

Saturday, December 20, 2014

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;
    }
}

No comments:

Post a Comment