85 最大矩形
https://leetcode.cn/problems/maximal-rectangle/
若matrix[i][j] == ‘1’,那么以该点为矩形的右下角
- 记
left[i][j]为第i行第j列元素左边连续1的个数(包括第i行第j列) - 那么矩形可以转换为若干个柱形,
left[i][j]为柱形的高度,题目就变成了84 求柱状图最大的柱形 - 宽度为k - i + 1,k为第i行前的第k行
换一下坐标轴,宽度就是代码中的高度,高度就是代码中的宽度
解法一:暴力枚举点
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
vector<vector<int>> left(n,vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == '1') {
left[i][j] = (j == 0 ? 0: left[i][j - 1]) + 1;
}
}
}
int ans = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(matrix[i][j] == '1'){
int w = left[i][j];
// 这里area初始化为w, 因为假设matrix[k][j]都为'0', 宽度至少为1
int area = w;
for(int k = i - 1; k >= 0; k--){
w = min(w, left[k][j]);
area = max(area, (i - k + 1) * w);
}
ans = max(ans, area);
}
}
}
return ans;
}
};
复杂度分析
时间复杂度:\(O(m^2n)\),其中 m 和 n 分别是矩阵的行数和列数。计算 left 矩阵需要 O(mn) 的时间。随后对于矩阵的每个点,需要 O(m) 的时间枚举高度。故总的时间复杂度为$ O(mn)+O(mn)⋅O(m)=O(m^2n)$。
空间复杂度:\(O(mn)\),其中 m 和 n 分别是矩阵的行数和列数。我们分配了一个与给定矩阵等大的数组,用于存储每个元素的左边连续 1 的数量。
解法二:单调栈
同84 一样,需要求出柱形图最小的高度(代码中为宽度)
与84不同之处在于,本题可以拆分为m列 柱形图,将84题的代码处理m次即可
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
vector<vector<int>> left(n, vector<int>(m, 0));
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(matrix[i][j] == '1')
left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
}
}
int ans = 0;
int len = n + 2;
// 枚举每一列
for(int j = 0; j < m; j++){
stack<int> stk;
int area = 0;
vector<int> ll(len);
ll[0] = 0;
ll[len - 1] = 0;
// 初始化别弄反了,是left[k - 1][j],不是left[j][k - 1]
for(int k = 1; k < len - 1; k++)
ll[k] = left[k - 1][j];
for(int i = 0; i < len; i++){
while(!stk.empty() && ll[i] < ll[stk.top()]){
int idx = stk.top();
stk.pop();
int w = i - stk.top() - 1;
area = max(area, w * ll[idx]);
}
stk.push(i);
}
ans = max(ans, area);
}
return ans;
}
};
复杂度分析
时间复杂度:O(mn),其中 m 和 n 分别是矩阵的行数和列数。计算 left 矩阵需要 O(mn) 的时间;对每一列应用柱状图算法需要 O(m) 的时间,一共需要 O(mn) 的时间。
空间复杂度:O(mn),其中 m 和 n 分别是矩阵的行数和列数。我们分配了一个与给定矩阵等大的数组,用于存储每个元素的左边连续 1 的数量。