Maximal Rectangle, Leetcode 解题笔记

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

这题又给跪了,面试时如果之前没见过,谁能想出最优解法?
最Naive的方法就是遍历矩阵,以每一个位置作为矩形的左上角,然后向右向下找1。直接摘抄别人代码:
来自:http://www.cnblogs.com/lichen782/p/leetcode_maximal_rectangle.html

/**
     * 以给出的坐标作为左上角,计算其中的最大矩形面积
     * @param matrix
     * @param row 给出坐标的行
     * @param col 给出坐标的列
     * @return 返回最大矩形的面积
     */
    private int maxRectangle(char[][] matrix, int row, int col) {
        int minWidth = Integer.MAX_VALUE;
        int maxArea = 0;
        for (int i = row; i < matrix.length && matrix[i][col] == '1'; i++) {
            int width = 0;
            while (col + width < matrix[row].length
                    && matrix[i][col + width] == '1') {
                width++;
            }
            if (width < minWidth) {// 如果当前宽度小于了以前的最小宽度,更新它,为下面的矩形计算做准备
                minWidth = width;
            }
            int area = minWidth * (i - row + 1);
            if (area > maxArea)
                maxArea = area;
        }
        return maxArea;
    }

    public int maximalRectangle(char[][] matrix) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int m = matrix.length;
        int n = m == 0 ? 0 : matrix[0].length;
        int maxArea = 0;
        for(int i = 0; i < m; i++){//row
            for(int j = 0; j < n; j++){//col
                if(matrix[i][j] == '1'){
                    int area = maxRectangle(matrix, i, j);
                    if(area > maxArea) maxArea = area;
                }
            }
        }
        return maxArea;
}

当然了,如果你把上面的代码写对了,恭喜你,但这还不算完。这种方法时间复杂度太高了,直接O(n^3)去了。那么最好的方法是什么呢?请先复习前一道题:Largest Rectangle in Histogram,其实就是同样的思路,只不过这次是以矩阵中每行为x轴,对于每个x,向上连续的1的个数为高,求最大矩形面积。

20232015-42cfb4fde2c34119b1811953e34d4193

public int maximalRectangle2(char[][] matrix) {
        int m = matrix.length;
        int n = m == 0 ? 0 : matrix[0].length;
        int[][] height = new int[m][n + 1];
        //actually we know that height can just be a int[n+1], 
        //however, in that case, we have to write the 2 parts together in row traverse,
        //which, leetcode just doesn't make you pass big set
        //所以啊,leetcode是喜欢分开写循环的,即使时间复杂度一样,即使可以节约空间
        int maxArea = 0;
        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;
                }
            }
        }
        for(int i = 0; i < m; i++){
            int area = maxAreaInHist(height[i]);
            if(area > maxArea){
                maxArea = area;
            }
        }
        return maxArea;
     }
     
     private int maxAreaInHist(int[] height){
         Stack<Integer> stack = new Stack<Integer>();
         int i = 0;
         int maxArea = 0;
         while(i < height.length){
             if(stack.isEmpty() || height[stack.peek()] <= height[i]){
                 stack.push(i++);
             }else {
                 int t = stack.pop();
                 maxArea = Math.max(maxArea, height[t] * (stack.isEmpty() ? i : i - stack.peek() - 1));
             }
         }
         return maxArea;
     }
Advertisements

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