leetcode85.最大矩形

Posted on | In |
Words count in article: 442 | Reading time ≈ 2

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

示例：

1
2
3
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

分析：

1
2
1、枚举矩形的边界，从边界出发统计连续1的个数，之后转化为求柱状图中的最大矩形
2、单调栈求最大面积

代码

  • C++

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
45
46
47
48
49
50
51
class Solution {
public:

    int longHeight(vector<int>& h) {
        int n = h.size();
        stack<int> stk;
        vector<int> left(n), right(n);

        for (int i = 0;i < n;i ++) {
            while (!stk.empty() && h[stk.top()] >= h[i]) stk.pop();
            if (stk.empty()) left[i] = -1;
            else left[i] = stk.top();
            stk.push(i);
        }

        stk = stack<int>();
        for (int j = n - 1;j >= 0;j --) {
            while (!stk.empty() && h[stk.top()] >= h[j]) stk.pop();
            if (stk.empty()) right[j] = n;
            else right[j] = stk.top();
            stk.push(j);
        }

        int res = 0;
        for (int i = 0;i < n;i ++)
            res = max(res, h[i] * (right[i] - left[i] - 1));

        return res;

    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<int>> f(n, vector<int>(m));

        for (int i = 0;i < n;i ++)
            for (int j = 0;j < m;j ++)
                if (matrix[i][j] == '1') {
                    if (i) f[i][j] = f[i - 1][j] + 1;
                    else f[i][j] = 1; // 边界0
                }        

        int res = 0;
        for (int i = 0;i < n;i ++) {
            res = max(res, longHeight(f[i]));
        }

        return res;
    }
};

[原题链接](85. 最大矩形 - 力扣（Leetcode）)

[相似题目](84. 柱状图中最大的矩形 - 力扣（Leetcode）)

0%