龙

哇咔咔

0%

LeetCode 85 Maximal Rectangle

发表于 分类于 Disqus：
Leetcode第85题，求矩阵中的最大长方形。

Description:

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

For example, given the following matrix:

1
2
3
4
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.

题目理解：

在矩阵中去找最小的长方形，初步想法是尝试用动态规划来做，但是实际上是不行的， 因为原问题的最优解好像并不能由它的子问题的最优解来构成。

然后就想能不能用什么搜索的方法来寻找，通过逐步扩大搜索范围来求解，并不知道怎么做。

突然想到将两行加在一起，例如下面两行，

1
2
1 0 1 0 0
1 0 1 1 1

加起来得到，

1
2 0 2 1 1

那么这两行的最大长方形要不就是2，要不就是衡向的三个1，那么如果是三行呢？

1
2
3
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1

加起来得到，

1
3 1 3 2 2

从这个结果可以看出，这里就将上面的矩阵表现成为了一个柱状图，值就是它的高度！！！

那么这不正好就是上一题84题所做的东西，求柱状图中的最大长方形。

于是就变得十分简单，将上一题的代码直接拿过来，就解决了问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int maximalRectangle(char[][] matrix) {
        if ( matrix == null || matrix.length == 0 ) return 0;
        int m = matrix.length, n = matrix[0].length, max = 0;
        int[] row_sum = new int[n];
        for ( int i = 0; i < m; i++ ) {
            for ( int j = 0; j < n; j++ )
                row_sum[j] = ('0' == matrix[i][j]) ? 0 : row_sum[j] + 1;
            int area = largestRectangleArea(row_sum);
            if ( area > max )
                max = area;
        }
        return max;
    }
    
    private int largestRectangleArea(int[] heights) {
        int max = 0, n = heights.length;
        int[] small_left = new int[n];
        int[] small_right = new int[n];
        small_left[0] = -1;
        small_right[n-1] = n;
        for ( int i = 1; i < n; i++ ) {
            int idx = i - 1;
            while ( idx >= 0 && heights[idx] >= heights[i] )
                idx = small_left[idx];
            small_left[i] = idx;
        }
        for ( int i = n - 2; i >= 0; i-- ) {
            int idx = i + 1;
            while ( idx < n && heights[idx] >= heights[i] )
                idx = small_right[idx];
            small_right[i] = idx;
        }
        for ( int i = 0; i < n; i++ ) {
            int area = (small_right[i] - small_left[i] - 1) * heights[i];
            if ( area > max )
                max = area;
        }
        return max;
    }
}

由于上一题的代码复杂度为O(n)，那么这里的复杂度就是O(n^2)。
运行时间：8ms。
击败：95.90%

image