Luobuyu's Blog

0%

85. 最大矩形

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 3.1k 阅读时长 ≈ 3 分钟
使用悬线法，复习悬线法。

85.最大矩形

题目描述：

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

数据范围：

$1\le row, cols \le 200$

题解：

使用悬线法或者循环加单调栈的做法。

悬线法：

使用 $left[i][j],right[i][j]$ 表示从 $i,j$ 向左和向右能遍历到的格子的数量。使用 $height[i][j]$ 表示从 $i,j$ 向上能遍历到的格子的数量。

由于 $left[i][j], right[i][j]$ 都是和行相关，更新也是在行内更新， $height[i][j]$ 与列相关。因此可以先循环行，然后在行数大于等于 $2$ 时更新 $height,left,right$ 。

其中：

$height[i][j]$ 是一根悬线， $left[i][j],right[i][j]$ 表示的是该长度的悬线左右最多能移动的长度。那么矩形的面积就是 $(right[i][j] + left[i][j] - 1) \times height[i][j]$ ，正方形的面积就是 $\min(right[i][j] + left[i][j] - 1, height[i][j])^2$ 。

最大正方形还有别的做法。可以使用 $dp[i][j]$ 表示以 $i,j$ 为右下角的正方形的最大边长。则 $dp[i][j] = \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])$ 。

单调栈：

首先看另一道题，84. 柱状图中最大的矩形 - 力扣（LeetCode），需要找到每个柱子的两侧第一个低于它的下标，可以在两侧用上哨兵。因为找第一个小于他的所以用单调增栈，每次遇到小于栈顶元素的，出栈，更新出栈元素的最右侧第一个小于它的下标。最后如果栈不为空就挨个出栈，更新出栈元素最左侧的第一个小于他的下标。

放到该题上，可以对每一行维护一下柱形图的高度，然后直接调用上面题目的函数就行解决。

代码：

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
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 2e2 + 10;
    const static int maxm = 2e2 + 10;
    const int INF = 0x3f3f3f3f;
    int height[maxn][maxm] = {};
    int left[maxn][maxm] = {};
    int right[maxn][maxm] = {};
    int maximalRectangle(vector<vector<char>> &matrix)
    {
        int n = matrix.size(), m = matrix[0].size();
        int ans = 0;
        for (int i = 1; i <= n; ++i)
        {
            for(int j = m; j >= 1; --j)
                if (matrix[i - 1][j - 1] == '1')
                    right[i][j] = right[i][j + 1] + 1;
            for(int j = 1; j <= m; ++j)
                if(matrix[i - 1][j - 1] == '1')
                    left[i][j] = left[i][j - 1] + 1;
            for (int j = 1; j <= m; ++j)
            {
                if (matrix[i - 1][j - 1] == '1')
                {
                    height[i][j] = height[i - 1][j] + 1;
                    if(i >= 2 && matrix[i - 2][j - 1] == '1')
                    {
                        left[i][j] = min(left[i][j], left[i - 1][j]);
                        right[i][j] = min(right[i][j], right[i - 1][j]);
                    }
                    ans = max(ans, (left[i][j] + right[i][j] - 1) * height[i][j]);
                }
            }
        }
        return ans;
    }
};
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
52
53
54
55
56
57
58
59
60
61
62
63
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    int largestRectangleArea(vector<int> &heights)
    {
        int n = heights.size();
        vector<int> st(n);
        int top = -1;
        int ans = 0;
        for (int i = 0; i < n; ++i)
        {
            while (top >= 0 && heights[st[top]] >= heights[i])
            {
                int h = heights[st[top]];
                int right = i - 1;
                --top;
                int left = top < 0 ? 0 : st[top] + 1;
                int w = right - left + 1;
                ans = max(ans, w * h);
            }
            st[++top] = i;
        }
        int size = st[top];
        while (top >= 0)
        {
            int h = heights[st[top]];
            int right = size;
            --top;
            int left = top < 0 ? 0 : st[top] + 1;
            int w = right - left + 1;
            ans = max(ans, w * h);
        }
        return ans;
    }
    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] += 1;
                else
                    heights[j] = 0;
            }
            ans = max(ans, largestRectangleArea(heights));
        }
        return ans;
    }
};