1,题目要求
Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.
Example:
Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6
给定填充0和1的2D二进制矩阵,找到仅包含1的最大矩形并返回其区域。
2,题目思路
对于这道题,计算一个矩阵内的最大的矩形面积。
在解决这个问题上,我们使用动态规划的思路来实现。
对于矩形的每个点(row, col), 我们计算:
- 改点上方的连续的‘1’往left、right方向延伸所能达到的最大的矩形的面积。
- **left:**向左可以延伸到的最左的位置
- **right:**向右可以延伸到的最右的位置+1
因为我们始终要保持一个矩形,因此,为了防止出现“凸”的情况,因此:
- 最左侧的坐标,我们取max
- 最右侧的坐标,我们取min
在遍历时,从上往下增加行数,每增加一行,根据当前节点是否是1,来对矩形的高度进行更新(height[j]++ 或者 height[j] = 0),然后,把当前行往上所有能够构成矩形的面积计算出来,这个面积的宽度取决于最大的满足矩形条件的连续的1的个数(right[j] - left[j]),高度则就是height[j],然后再与最大值比较,记录最大值。
遍历到最后一行时,就找到最终结果了。
3,代码实现
1,带有注释、便于理解
static const auto s = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.empty())
return 0;
const int m = matrix.size();
const int n = matrix[0].size();
vector<int> left (n, 0);
vector<int> right (n, n);
vector<int> height (n, 0);
int maxArea = 0;
for(int i = 0;i<m;i++){
int curLeft = 0, curRight = n;
//计算当前节点对应的最大高度
for(int j = 0;j<n;j++){
if(matrix[i][j] == '1')
height[j]++;
else
height[j] = 0;
}
//计算当前节点向左所能达到的可行的最远位置,默认为0,即达到最左
for(int j = 0;j<n;j++){
if(matrix[i][j] == '1')
left[j] = max(left[j], curLeft); //取前几行的最远索引位置和当前最远索引位置的最大值,即最靠近当前节点的左侧位置,以保证不会出现'凸'的情况
else{
left[j] = 0; //恢复为初值,反正当前点也一定不会再可行矩形内
curLeft = j+1;
}
}
//计算当前节点向右所能达到的可行的最远位置,默认为n,即达到最右
for(int j = n-1;j>=0;j--){
if(matrix[i][j] == '1')
right[j] = min(right[j], curRight); //同理,此时是利用去min,同样保证不会出现'凸'的情况
else{
right[j] = n;
curRight = j;
}
}
//计算此时最大的矩形面积
for(int j = 0;j<n;j++)
maxArea = max(maxArea, (right[j] - left[j])*height[j]);
}
return maxArea;
}
};
2,原理相同,简化代码
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.empty())
return 0;
const int m = matrix.size();
const int n = matrix[0].size();
vector<int> left(n, 0), right(n, n), height(n, 0);
int maxArea = 0;
for(int i = 0;i<m;i++){
int curLeft = 0, curRight = n;
for(int j = n-1;j>=0;j--)
if(matrix[i][j] == '1') right[j] = min(right[j], curRight);
else{ right[j] = n, curRight = j;}
for(int j = 0;j<n;j++){
if(matrix[i][j] == '1'){
height[j]++;
left[j] = max(left[j], curLeft);
}
else{
height[j] = 0;
left[j] = 0, curLeft = j+1;
}
maxArea = max(maxArea, (right[j] - left[j])*height[j]);
}
}
return maxArea;
}
};