Leetcode 85. 最大矩形 maximal rectangle

目录

1. 暴力
2. 转换为多个 84 题的问题，对每一行使用递增栈方法
3. 动态规划

题目链接
这个题目是 84 题的升级版
84 题题解

暴力

暴力，能过(但是 84 题用类似的策略是不行的）

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        n = len(matrix)
        if n == 0: return 0
        m = len(matrix[0])
        max_l = [[0] * m for i in range(n)]
        for i in range(n):
            cur = 0
            for j in range(m):
                if matrix[i][j] == '1':
                    cur += 1
                else:
                    cur = 0
                max_l[i][j] = cur
        ans = 0
        for i in range(n):
            for j in range(m):
                if matrix[i][j] == '1':
                    minl = max_l[i][j]
                    for k in range(i, n):
                        if matrix[k][j] == '0': break
                        minl = min(minl, max_l[k][j])
                        ans = max(ans, minl * (k-i+1))
        return ans

max_l 是每个点向左延伸最多有多少个格子。

计算 max_l 矩阵要遍历 n × m。

然后再从每个点开始，看这个点作为右上顶点的矩形的最大面积，这个又需要沿着 n 方向遍历。

所以时间复杂度是 O（n^2 × m）

转换为多个 84 题的问题，对每一行使用递增栈方法

上面的方法 max_l 的每一列都相当于 84 题中的一个问题。
下面的代码直接拿来了 84 题的代码，对每一行调用了那个函数。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        hs = [0] + heights + [0]
        s = []
        ans = 0
        for i, h in enumerate(hs):
            while s and hs[s[-1]] > h:
                j = s.pop()
                ans = max(ans, hs[j] * (i-s[-1]-1))
            s.append(i)
        return ans

    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        n = len(matrix)
        if n == 0: return 0
        m = len(matrix[0])
        dp = [int(i) for i in matrix[0]]
        ans = self.largestRectangleArea(dp)
        for i in range(1, n):
            for j in range(m):
                if matrix[i][j] == '1':
                    dp[j] += 1
                else:
                    dp[j] = 0
            ans = max(ans, self.largestRectangleArea(dp))
        return ans

动态规划

从每个为 1 的位置，我们可以计算当前位置上这样的矩形的面积:

1. 高度尽量往上延伸（到上面第一个 0 或者边界）
2. 左右尽量宽

那么全局最大的面积一定在这里面。

任意一点都有一个 h 高度，l 左边界，r 右边界。矩形面积是 h × （r - l)则里的 l 是该点左边第一个 0 （或边界）的右边一个元素的下标。r 是最右边的一个 0 或者（边界）下标。

这里 h 好计算，当前是 0，h 设为 0，不是 0 则 h 是上一行的 h 加一。

l 和 r，以 l 为例，始终维护当前左边界，（初始为 0）如果当前是 1，l 是当前左边界和上一行左边界的最大值（因为我们要看整个左边界的情况）;如果当前是 0，就更新当前左边界为当前下标加一，l 设为 0。（这里设为 0 起始并不是真的 0，而且对本行该位置计算不起作用（因为当前位置 h 肯定为 0，一乘就是 0 了）主要是相当于重置了状态，下一行的左边界就不受本行限制了。

r 的情况类似。

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        n = len(matrix)
        if n == 0: return 0
        m = len(matrix[0])
        l = [0] * m
        r = [m] * m
        h = [0] * m
        ans = 0
        for i in range(n):
            for j in range(m):
                if matrix[i][j] == '1': 
                    h[j] += 1
                else: 
                    h[j] = 0
            cur = 0
            for j in range(m):
                if matrix[i][j] == '1': 
                    l[j] = max(cur, l[j])
                else:
                    cur = j + 1
                    l[j] = 0
            cur = m
            for j in range(m-1, -1, -1):
                if matrix[i][j] == '1':
                    r[j] = min(cur, r[j])
                else:
                    r[j] = m
                    cur = j
            for j in range(m):
                ans = max(ans, h[j] * (r[j] - l[j]))
        return ans