85. 最大矩形

转载自这里写链接内容

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例:

输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6

思路

和最大矩形那个差不多的思路，这里就是从上到下一行的一行的扫描，高度的话碰到1就是1，如果不是就归零。

class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.size()==0||matrix[0].size()==0) return 0;
int n=matrix.size(),m=matrix[0].size();
vector<int> height(m,0);
int res=0;
for(int i=0;i<n;i++){
stack<int> area;
for(int j=0;j<m;j++){
if(matrix[i][j]=='0') height[j]=0;//要连续才会累加高度
else height[j]+=1;
if(area.empty()||height[j]>height[area.top()]) area.push(j);
else{
while(!area.empty()&&height[area.top()]>=height[j]){
int tmp=area.top();
area.pop();
int length=0;
if(area.empty()) length=j;
else length=j-area.top()-1;
res=max(res,height[tmp]*length);
}
area.push(j);
}
}
while(!area.empty()){
int tmp=area.top();
area.pop();
int length=0;
if(area.empty()) length=m;
else length=m-area.top()-1;
res=max(res,height[tmp]*length);
}
}
return res;
}
};

最后

以上就是大胆鞋子为你收集整理的85. 最大矩形85. 最大矩形的全部内容，希望文章能够帮你解决85. 最大矩形85. 最大矩形所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。