LC 85. 最大矩形

题目描述

这是 LeetCode 上的 85. 最大矩形 ，难度为 困难。

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

示例 1：

1
2
3
4
5
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

输出：6

解释：最大矩形如上图所示。

示例 2：
1
2
3
输入：matrix = []

输出：0

示例 3：
1
2
3
输入：matrix = [["0"]]

输出：0

示例 4：
1
2
3
输入：matrix = [["1"]]

输出：1

示例 5：
1
2
3
输入：matrix = [["0","0"]]

输出：0

提示：

  • $rows = matrix.length$
  • $cols = matrix[0].length$
  • $1 <= row, cols <= 200$
  • matrix[i][j] 为 '0' 或 '1'

前缀和 + 单调栈

为了方便，我们令 matrix 为 mat，记矩阵的行高为 $n$，矩阵的列宽为 $m$。

定义坐标系 : 左上角坐标为 $(1, 1)$，右下角坐标为 $(n, m)$。

我们将 mat 的每一行作为基准，以基准线为起点，往上连续 $1$ 的个数为高度。

以题目样例进行说明：

image.png

  1. 红框部分代表「以第一行作为基准线，统计每一列中基准线及以上连续 $1$ 的个数」，此时只有第一行，可得：$[1, 0, 1, 0, 0]$
  2. 黄框部分代表「以第二行作为基准线，统计每一列中基准线及以上连续 $1$ 的个数」，此时有第一行和第二行，可得：$[2, 0, 2, 1, 1]$
  3. 蓝框部分代表「以第三行作为基准线，统计每一列中基准线及以上连续 $1$ 的个数」，此时有三行，可得：$[3, 1, 3, 2, 2]$
    …

将原矩阵进行这样的转换好处是 : 对于原矩中面积最大的矩形，其下边缘必然对应了某一条基准线，从而将问题转换为（题解）84. 柱状图中最大的矩形 。

预处理基准线数据可以通过前缀和思想来做，构建一个二维数组 sum（为了方便，我们令二维数组下标从 $1$ 开始）并从上往下地构造：

当有了 sum 之后，则是和 （题解）84. 柱状图中最大的矩形 一样的做法 : 枚举高度 + 单调栈。

Java 代码：

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
class Solution {
    public int maximalRectangle(char[][] mat) {
        int n = mat.length, m = mat[0].length, ans = 0;
        int[][] sum = new int[n + 10][m + 10];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = mat[i - 1][j - 1] == '0' ? 0 : sum[i - 1][j] + 1;
            }
        }
        int[] l = new int[m + 10], r = new int[m + 10];
        for (int i = 1; i <= n; i++) {
            int[] cur = sum[i];
            Arrays.fill(l, 0); Arrays.fill(r, m + 1);
            Deque<Integer> d = new ArrayDeque<>();
            for (int j = 1; j <= m; j++) {
                while (!d.isEmpty() && cur[d.peekLast()] > cur[j]) r[d.pollLast()] = j;
                d.addLast(j);
            }
            d.clear();
            for (int j = m; j >= 1; j--) {
                while (!d.isEmpty() && cur[d.peekLast()] > cur[j]) l[d.pollLast()] = j;
                d.addLast(j);
            }
            for (int j = 1; j <= m; j++) ans = Math.max(ans, cur[j] * (r[j] - l[j] - 1));
        }
        return ans;
    }
}

TypeScript 代码：
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
function maximalRectangle(mat: string[][]): number {
    const n = mat.length, m = mat[0].length
    const sum = new Array<Array<number>>(n + 10)
    sum[0] = new Array<number>(m + 10).fill(0)
    for (let i = 1; i <= n; i++) {
        sum[i] = new Array<number>(m + 10).fill(0)
        for (let j = 1; j <= m; j++) {
            sum[i][j] = mat[i - 1][j - 1] == '0' ? 0 : sum[i - 1][j] + 1
        }
    }
    let ans = 0
    const l = new Array<number>(m + 10), r = new Array<number>(m + 10)
    const stk = new Array<number>(m + 10).fill(0)
    let he = 0, ta = 0
    for (let i = 1; i <= n; i++) {
        const cur = sum[i]
        l.fill(0); r.fill(m + 1)
        he = ta = 0
        for (let j = 1; j <= m; j++) {
            while (he < ta && cur[stk[ta - 1]] > cur[j]) r[stk[--ta]] = j
            stk[ta++] = j
        }
        he = ta = 0
        for (let j = m; j >= 1; j--) {
            while (he < ta && cur[stk[ta - 1]] > cur[j]) l[stk[--ta]] = j
            stk[ta++] = j
        }
        for (let j = 1; j <= m; j++) ans = Math.max(ans, cur[j] * (r[j] - l[j] - 1))
    }
    return ans
}

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
class Solution:
    def maximalRectangle(self, mat: List[List[str]]) -> int:
        n, m, ans = len(mat), len(mat[0]), 0
        psum = [[0] * (m + 10) for _ in range(n + 10)]
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                psum[i][j] = 0 if mat[i - 1][j - 1] == '0' else psum[i - 1][j] + 1
        stk = [0] * (m + 10)
        he, ta = 0, 0
        for i in range(1, n + 1):
            cur = psum[i]
            l, r = [0] * (m + 10), [m + 1] * (m + 10)
            he = ta = 0
            for j in range(1, m + 1):
                while he < ta and cur[stk[ta - 1]] > cur[j]:
                    ta -= 1
                    r[stk[ta]] = j
                stk[ta] = j
                ta += 1
            he = ta = 0
            for j in range(m, 0, -1):
                while he < ta and cur[stk[ta - 1]] > cur[j]:
                    ta -= 1
                    l[stk[ta]] = j
                stk[ta] = j
                ta += 1
            for j in range(1, m + 1):
                ans = max(ans, cur[j] * (r[j] - l[j] - 1))
        return ans

  • 时间复杂度：$O(n \times m)$
  • 空间复杂度：$O(n \times m)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.85 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

前缀和 单调栈

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！