leetcode85：最大矩形

题目链接

leetcode

题目描述

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

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void printArray(vector<vector<char>>& arr)
{
	for (auto x : arr) {
		for (auto y : x) {
			cout << y << " ";
		}
		cout << endl;
	}
}

/*
    最原始的方法，枚举每个可能的矩形。
    枚举矩形所有可能的左上角坐标和右下角坐标，并检查该矩形是否符合要求。
    然而该方法的时间复杂度过高，不能通过所有的测试用例，必须寻找其他方法。

    先计算出矩阵的每个元素的左边连续 1 的数量
    然后枚举每个元素，计算其左边连续 1 的数量，并计算其右边连续 1 的数量。
    计算矩形的面积，取最大值。

    时间复杂度：O(m^2*n)
        其中 m 和 n 分别是矩阵的行数和列数。
        计算 left 矩阵需要 O(mn) 的时间。
        对于矩阵的每个点，需要 O(m) 的时间枚举高度。
        故总的时间复杂度为 O(mn) + O(mn)*O(m) = O(m^2*n)。
    空间复杂度：O(mn)
        一个与给定矩阵等大的数组，存储每个元素的左边连续 1 的数量。
*/
class Solution_0 {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty()) return 0;
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> left(m, vector<int>(n, 0));

        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                if (matrix[i][j] == '1') {
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }
            }
        }

        int res = 0;
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                if (matrix[i][j] == '0') continue;
                int width = left[i][j];
                int area = width;
                for (int k = i - 1; k >= 0; k --) {
                    width = min(width, left[k][j]);
                    area = max(area, (i - k + 1) * width);
                }
                res = max(res, area);
            }
        }

        return res;
    }
};

/*
    单调栈

    1.将柱状图中最大的矩形扩展到二维。
    2.一行行考虑，一行内所有柱形条的高度是当前位置(i, j)往上延伸的最大高度。
    3.套用柱状图中最大的矩形问题的单调栈算法。

    时间复杂度：O(mn)
        枚举每一行的时间复杂度是 O(m)，行内单调栈的时间复杂度是 O(n)，故总时间复杂度为 O(mn)。
    空间复杂度：O(mn)
        二维数组需要空间为 O(m*n)，单调栈需要空间为 O(n)。
*/
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int m = matrix.size(), n = matrix[0].size();

        vector<vector<int>> h(m, vector<int>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    h[i][j] = (i == 0 ? 0 : h[i - 1][j]) + 1;
                }
            }
        }

        int res = 0;
        for (int i = 0; i < m; i++) {
            // leetcode84. largestRectangleArea
            vector<int>& heights = h[i];
            heights.push_back(-1); // 在数组末尾添加高度-1，使得栈中所有数字在最后出栈
            
            stack<int> stk;
            int area = 0;
            for (int j = 0; j <= n; j++) {
                while (!stk.empty() && (heights[j] <= heights[stk.top()])) {
                    int index = stk.top(); stk.pop();
                    if (stk.empty()) {
                        area = max(area, heights[index] * j);
                    } else {
                        area = max(area, heights[index] * (j - stk.top() - 1));
                    }
                }
                stk.push(j);
            }
            res = max(res, area);
        }

        return res;
    }
};

/*
    思路同上，优化空间

    时间复杂度：O(mn)
        枚举每一行的时间复杂度是 O(m)，行内单调栈的时间复杂度是 O(n)，故总时间复杂度为 O(mn)。
    空间复杂度：O(n)
        数组需要空间为 O(n)，单调栈需要空间为 O(n)。
*/
class Solution_2 {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int m = matrix.size(), n = matrix[0].size();

        vector<int> h(n + 1, 0);
        h[n] = -1;
        int res = 0;
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                h[j] = matrix[i][j] == '0' ? 0 : h[j] + 1;
            }

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

        return res;
    }
};

int main() {
    Solution solution;
    vector<vector<char>> matrix = {
        {'1', '0', '1', '0', '0'},
        {'1', '0', '1', '1', '1'},
        {'1', '1', '1', '1', '1'},
        {'1', '0', '0', '1', '0'}
    };
    printArray(matrix);
    int result = solution.maximalRectangle(matrix);
    cout << "The maximal rectangle area is: " << result << endl;

    return 0;
}
#leetcode
leetcode85：最大矩形
https://lcf163.github.io/2023/12/03/leetcode85：最大矩形/
作者
乘风的小站
发布于
2023年12月3日
许可协议