[leetcode] Maximal Rectangle | 0101组成的矩阵，求里面全是1的矩形的最大面积

Posted by: lexigrey on: October 19, 2013

• In: leetcode
• 4 Comments

这个题挺吓人的，后来bf给讲明白了然后记得葫芦半片的，今天自己重新想了想，还是做出来了也通过了。不过是O(M * M * N的速度，没有网上说的O(M*N)，忍了，反正也能pass oj.

算法：

1. 先用dp求一个新矩阵，d[i][j]表示以(i, j)结尾有几个连续1（在当前row)。
2. 然后遍历这个新矩阵，在每个cell，都看看“宽度是d[i][j]的矩阵最多能有多高？“，也就是往上expand到宽度变窄为止，往下expand到宽度变窄为止，然后总高度×当前宽度就是d[i][j]所属于的矩阵的最大面积。这就是个O(M * N) * O(M)。

当时给讲的时候觉得这怎么是人类能想出来的呢？然后bf说你把二维降成一维怎么做，不也是找以当前结束的1有多长吗。然后恍然大悟，这题还是有救的。题目本身写起来细节不多，不容易出bug，两遍就过了很开心～

public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0)
        return 0;
    int res = 0;
    int m = matrix.length, n = matrix[0].length;
    int[][] d = new int[m][n];
    for (int i = 0; i < m; i++) {
        d[i][0] = matrix[i][0] - '0';
        for (int j = 1; j < n; j++) {
            d[i][j] = matrix[i][j] == '1' ? d[i][j - 1] + 1 : 0;
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            res = Math.max(res, expand(d, i, j));
        }
    }
    return res;
}
private int expand(int[][] d, int I, int J) {
    int height = 0;
    int width = d[I][J];
    //go up
    for (int i = I - 1; i >= 0; i--) {
        if (d[i][J] >= width) {
            height++;
        } else {
            break;
        }
    }
    //go down
    for (int i = I; i < d.length; i++) {
        if (d[i][J] >= width) {
            height++;
        } else {
            break;
        }
    }
    return width * height;
}

Tags: EndWith, matrix