题目
困难
相关标签
相关企业
给定一个仅包含 0
和 1
、大小为 rows x cols
的二维二进制矩阵,找出只包含 1
的最大矩形,并返回其面积。
示例 1:
输入:matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出:6 解释:最大矩形如上图所示。
示例 2:
输入:matrix = [["0"]] 输出:0
示例 3:
输入:matrix = [["1"]] 输出:1
提示:
rows == matrix.length
cols == matrix[0].length
1 <= row, cols <= 200
matrix[i][j]
为'0'
或'1'
通过次数 198.2K
提交次数 359.2K
通过率 55.2%
思路
把值为1的方格当作一个正方形,把某一层的每个方格作为底,该方格以及上方连续1的个数就是以该方格为底的矩形的面积,这样最大矩形面积就变成了以最下面一层方格作为底,最大柱状图的面积,就转化成了T84。
代码
class Solution {
public:
int largestRectangleArea(vector<int>& heights){
heights.push_back(-1);
stack<int> stk;
int ans=0;
for(int i=0;i<heights.size();i++){
//当遇到右边界时
while(!stk.empty() && heights[i]<heights[stk.top()]){
int tall=heights[stk.top()];
stk.pop();
int left=stk.empty() ? -1:stk.top();
ans=max(ans,(i-left-1)*tall);
}
stk.push(i);
}
return ans;
}
int maximalRectangle(vector<vector<char>>& matrix) {
int rows=matrix.size();
int cols=matrix[0].size();
vector<vector<int>> heights(rows,vector<int>(cols,0));
for(int i=0;i<cols;i++){
if(matrix[0][i]=='1') heights[0][i]=1;
}
for(int i=1;i<rows;i++){
for(int j=0;j<cols;j++){
if(matrix[i][j]=='1') heights[i][j]=heights[i-1][j]+1;
}
}
int ans=0;
for(int i=0;i<rows;i++){
ans=max(ans,largestRectangleArea(heights[i]));
}
return ans;
}
};