Leetcode解题-Maximal Rectangle

发表于   |   分类于   |  

描述

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

分析

这道题难度颇大，主题人出来我保证不打死你，双向动态规划可解，分析懒得写了，直接看这篇文章。

代码

Python

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
class Solution(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        m = len(matrix)
        if m == 0:
            return 0
        n = len(matrix[0])
        if n == 0:
            return 0
        H = [0] * n
        L = [0] * n
        R = [n] * n
        max_area = 0
        for i in xrange(m):
            left = 0
            right = n
            for j in xrange(n):
                if matrix[i][j] == '1':
                    H[j] += 1
                    L[j] = max(L[j], left)
                else:
                    left = j + 1
                    H[j] = 0
                    L[j] = 0
                    R[j] = n
            for j in xrange(n - 1, -1, -1):
                if matrix[i][j] == '1':
                    R[j] = min(R[j], right)
                    max_area = max(max_area, H[j] * (R[j] - L[j]))
                else:
                    right = j
        return max_area

热评文章