Maximal Rectangle

这道题刚开始看完全没有头绪,怎么样才能算出最大矩形的面积呢?最简单的想法就是全部扫一遍,从左上角那个点开始,扫整个矩阵,还是很麻烦。

这道题下面一道题连着的就是histogram的那道题,其实找矩阵里的最大长方形和找historgram中最大的长方形不是一样的吗,只不过矩阵有n行而historgram只有一行而已。

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

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0)
            return 0;
        int [][] h = new int[matrix.length][matrix[0].length];
        for (int j = 0; j < matrix[0].length; j++)
        {
            int curr = 0;
            for (int i = matrix.length-1; i >= 0 ; i--) // collect hight of the historgram below each line.
            {
                if (matrix[i][j] == '1')
                    curr++;
                else
                    curr = 0;
                h[i][j] = curr;
            }
        }
        
        int maxArea = 0;
        for (int i = 0; i < matrix.length; i++)
        {
            maxArea = Math.max(maxArea, findMaxRectHistogram(h[i]));
        }
        return maxArea;
    }
    
    public int findMaxRectHistogram(int [] height)
    {
        Stack<Integer> s = new Stack<Integer>();
        int maxArea = 0;
        for (int i = 0; i < height.length; i++)
        {
            if(s.isEmpty() || height[i] >= height[s.peek()])
            {
                s.push(i);
            }
            else
            {
                int t = s.pop();
                if (s.isEmpty()) // go all the way to 0
                    maxArea = Math.max(maxArea, height[t] * i);
                else // go to the last smallest element
                    maxArea = Math.max(maxArea, height[t] * (i - s.peek() - 1));
                i--;// no need to ++ if pops from stack, compensate the ++ in the for loop
            }
        }
         
        while(!s.isEmpty())// when all the elements has been scaned, pop everything left in the stack
        {
                int t = s.pop();
                if (s.isEmpty()) // go all the way to 0
                    maxArea = Math.max(maxArea, height[t] * (height.length));
                else // go to the last smallest element
                    maxArea = Math.max(maxArea, height[t] * (height.length - s.peek() - 1));
        }  
        return maxArea;
    }
}

Second Submission:

This problem use exactly the solution of largest rectangle in histogram. The problem came down to how to generate the histogram based on the 2D matrix.
The idea is to scan through col 0 ~ col.length, and for each col, accumulate the 1s on each row from 0 ~ row.length. Then we get another matrix h[][]. Each element h[r][c] contains the number of continuous 1s above each row r on col c. Then we can use the result from the largest rectangle in histogram to get the max area

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0)
            return 0;
        int [][] h = new int [matrix.length][matrix[0].length]; // number of rows
        for (int c = 0; c < matrix[0].length; c++) {
            int curr = 0;
            for (int r = 0; r < matrix.length; r++) {
                if (matrix[r][c] == '1')
                    curr++;
                else
                    curr = 0;
                h[r][c] = curr;
            }
        }
        int maxArea = 0;
        for (int r = 0; r < matrix.length; r++) {
            maxArea = Math.max(maxArea, largestRectangleArea(h[r]));
        }
        return maxArea;
    }
    public int largestRectangleArea(int[] height) {
        int [] h = new int [height.length + 1];
        for (int i = 0; i < height.length; i++) {
            h[i] = height[i];
        }
        h[h.length-1] = 0; // put 0 as the last element pop everything from the stack at the end
        Stack<Integer> s = new Stack<Integer>();
        int maxArea = 0;
        for (int i = 0; i < h.length; i++) {
            if (s.isEmpty()) {
                s.push(i);
            }
            else {
                if (h[i] >= h[s.peek()]) {
                    s.push(i);
                }
                else { // height[i] < s.peek();
                    int temp = s.pop();
                    int width = s.isEmpty()? i : (i-s.peek()-1);
                    maxArea = Math.max(maxArea, width*h[temp]);
                    i--;// i stay the same
                }
            }
        }
        return maxArea;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s