本文最后编辑于 前，其中的内容可能需要更新。
题目描述：
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 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
解释：最大矩形如上图所示。
|
示例 2：
示例 3：
1
2
| 输入：matrix = [["0"]]
输出：0
|
示例 4：
1
2
| 输入：matrix = [["1"]]
输出：1
|
示例 5：
1
2
| 输入：matrix = [["0","0"]]
输出：0
|
提示：
rows == matrix.lengthcols == matrix[0].length0 <= row, cols <= 200matrix[i][j] 为 '0' 或 '1'
链接：
https://leetcode-cn.com/problems/maximal-rectangle
题目分析
做这道题之前先看看与之关联的上一道题 Leetcode 84.柱状图中最大的矩形。我们可以发现，如果我们按照每一列的顺序维护 heights，就可以复用上一题的代码。就像下面这样。这样是可以遍历所有可能存在的矩形的，因此得到的答案就是最终答案。
PS：下面的代码中 largestRectangleArea 函数来自上一题，使用的是单调栈的做法，具体过程可以参阅上一题题解。
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
| class Solution {
int largestRectangleArea(vector<int>& heights) {
int result = 0;
stack<pair<int, int>> s;
s.push({-1, 0});
heights.push_back(0);
for(int i = 0; i < heights.size(); i++){
while(heights[i] < s.top().second){
int height = s.top().second;
s.pop();
result = max(result, (i - s.top().first - 1) * height);
}
s.push({i, heights[i]});
}
return result;
}
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.size() == 0) return 0;
int maxArea = 0;
vector<int> heights(matrix[0].size(), 0);
for(int i = 0; i < matrix.size(); i++){
for(int j = 0; j < matrix[0].size(); j++){
if(matrix[i][j] == '1'){
heights[j]++;
}
else heights[j] = 0;
}
maxArea = max(maxArea, largestRectangleArea(heights));
}
return maxArea;
}
};
|
时间复杂度：$O(mn)$，其中 $m、n$ 分别是矩阵的行数和列数。我们遍历矩阵的一行进行一次处理，而处理的函数时间复杂度是 $O(n)$。因此总的时间复杂度就是 $O(mn)$。
空间复杂度：$O(n)$，其中 $n$ 是矩阵的列数。因为我们需要维护一个 heights 数组，大小为 $O(n)$，并且进行处理的 largestRectangleArea 函数也需要 $O(n)$ 的栈空间。