LeetCode85 最大矩形

发表于 | 分类于 |
字数统计: 280 | 阅读时长 ≈ 1

链接: https://leetcode-cn.com/problems/maximal-rectangle/

题意

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

解法

把每一列的高度进行累计，每一行当作底部，问题就可以转换成求最大的矩形面积(LeetCode84)
对每一行进行统计，计算以当前行作为底的最大面积，计算出最大值
很巧妙的转换

代码

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
class Solution {
public:
    int solve(vector<int> heights) {
        vector<int> stk;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        int n = heights.size(), ret = 0;
        for (int i = 0; i < n; i++) {
            while(stk.size() && heights[stk.back()] > heights[i]) {
                int cur = stk.back();
                stk.pop_back();
                int r = i - 1, l = stk.back() + 1;
                ret = max(ret, (r - l + 1) * heights[cur]);
            }
            stk.push_back(i);
        }
        return ret;
    }
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        vector<int> heights(m);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == '1')  {
                    heights[j]++;
                }
                else {
                    heights[j] = 0;
                }
            }
            ans = max(ans, solve(heights));
        }
        return ans;
    }
};