LeetCode 85. 最大矩形（难）

84题的改进，从单个直方图变成多个直方图。每行看成一个直方图，累加height，注意判断遇到0的情况即可。

题目

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例

Example:

1
2
3
4
5
6
7
8
Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

:artificial_satellite: 考察知识点

动态规划、哈希表、数组、栈

核心思想

方法一、基于栈的方法
本题是 84. 柱状图中最大的矩形 的扩展，这道题的二维矩阵每一行都可以看做一个直方图，输入矩阵有多少行，就可以形成多少个直方图，对每个直方图都调用 84题 中的方法，就可以得到最大的矩形面积。由于题目限定了输入矩阵的字符只有 '0' 和 '1' 两种，所以处理起来也相对简单。方法是，对于每一个点，如果是 ‘0’，则赋0，如果是 ‘1’，就赋之前的 height 值加上1。
这里遇到 '0' 代表之前height数组在该位置上的累加都无效了，就赋0，这样就解决了对齐问题。

Snipaste_2020-03-22_12-16-20.png

方法二、动态规划

解法一 暴力求解 该方法本质上是 84 - 柱状图中最大的矩形 题中优化暴力算法的复用。挺复杂的，不推荐。

解法二 寻找每个点的最大高度
想象一个算法，对于每个点我们会通过以下步骤计算一个矩形：

  • 不断向上方遍历，直到遇到“0”，以此找到矩形的最大高度。
  • 向左右两边扩展，直到无法容纳矩形最大高度。
    例如，找到黄色点对应的矩形：

492476afc9693ce2cb7352c9c29094508573b4635b121633eafb07c382115141-image.png

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
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        res = 0
        st = []
        heights.append(0)
        i = 0
        while i < len(heights):
            if not len(st) or heights[st[-1]] < heights[i]:
                st.append(i)
            else:
                cur = st.pop()
                width = i if not len(st) else (i - st[-1] - 1)
                res = max(res, heights[cur] * width)
                i -= 1
            i += 1
        return res

    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        matrix = [[int(x) for x in row] for row in matrix]
        sub_matrix = []
        for row in matrix:
            sub_matrix.append(self.largestRectangleArea(row))
        res = self.largestRectangleArea(sub_matrix)
        return res

这种写法，解决不了 输入：[["0","1"],["1","0"]]，预期：1，这种测试用例，存在对齐问题。

  • 方法一解决对齐问题的解法
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
42
43
44
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        res = 0
        st = []
        heights.append(0)
        i = 0
        while i < len(heights):
            if not len(st) or heights[st[-1]] < heights[i]:
                st.append(i)
            else:
                cur = st.pop()
                width = i if not len(st) else (i - st[-1] - 1)
                res = max(res, heights[cur] * width)
                i -= 1  
            i += 1
        return res

    def maximalRectangle(self, matrix):
        if not len(matrix) or not len(matrix[0]):  return 0
        res = 0
        heights = [0 for _ in range(len(matrix[0]))]
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                heights[j] = 0 if matrix[i][j] == "0" else (1 + heights[j])  # 注意这里，
            res = max(res, self.largestRectangleArea(heights))
        return res

Input = [
    [
        ["1","0","1","0","0"],
        ["1","0","1","1","1"],
        ["1","1","1","1","1"],
        ["1","0","0","1","0"]
    ],
    [["0","1"],["1","0"]]
]
Answer = [6, 1]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)): 
        print("-"*50)
        reslut = solution.maximalRectangle(Input[i])
        print(reslut == Answer[i])

时间复杂度：\(O(m \times n^2)\)，m是行数，n是列数。
空间复杂度 : \(O(n)\)。我们声明了长度等于列数的数组，用于存储每一行的宽度。 执行用时 :162 ms, 在所有 Python3 提交中击败了71.60%的用户
内存消耗 :14.2 MB, 在所有 Python3 提交中击败了5.06%的用户

  • 方法二动态规划的实现

解法一的实现

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        maxarea = 0
        dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == '0': continue
                width = dp[i][j] = dp[i][j-1] + 1 if j else 1
                for k in range(i, -1, -1):
                    width = min(width, dp[k][j])
                    maxarea = max(maxarea, width * (i-k+1))
        return maxarea

时间复杂度 : \(O(N^2 \times M)\)。由于需要遍历同一列中的值，计算每个点对应最大面积需要 \(O(N)\)。对全部 \(N \times M\)个点都要计算，因此总共\(O(N) * O(N \times M) = O(N^2 \times M)\)
空间复杂度 : \(O(N \times M)\)。我们分配了一个等大的数组，用于存储每个点的最大宽度。 执行用时 :2764 ms, 在所有 Python3 提交中击败了5.02%的用户
内存消耗 :14.4 MB, 在所有 Python3 提交中击败了5.06%的用户

解法二的实现

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
class Solution:

    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix: return 0

        m = len(matrix)
        n = len(matrix[0])

        left = [0] * n # initialize left as the leftmost boundary possible
        right = [n] * n # initialize right as the rightmost boundary possible
        height = [0] * n

        maxarea = 0

        for i in range(m):

            cur_left, cur_right = 0, n
            # update height
            for j in range(n):
                if matrix[i][j] == '1': height[j] += 1
                else: height[j] = 0
            # update left
            for j in range(n):
                if matrix[i][j] == '1': left[j] = max(left[j], cur_left)
                else:
                    left[j] = 0
                    cur_left = j + 1
            # update right
            for j in range(n-1, -1, -1):
                if matrix[i][j] == '1': right[j] = min(right[j], cur_right)
                else:
                    right[j] = n
                    cur_right = j
            # update the area
            for j in range(n):
                maxarea = max(maxarea, height[j] * (right[j] - left[j]))

        return maxarea

时间复杂度 : \(O(N \times M)\)。每次对于N的迭代我们会对M迭代常数次。
空间复杂度 : \(O(M)\)， M 是我们保留的额外数组的长度。
执行用时 :108 ms, 在所有 Python3 提交中击败了83.42%的用户
内存消耗 :14.1 MB, 在所有 Python3 提交中击败了5.06%的用户

有效语法糖

LeetCode官方题解
Grandeyang