leetcode[85]Maximal Rectangle
5109 ワード
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
class Solution {
public:
int largestRectangleArea(vector<int> &height)
{
if(height.empty())return 0;
height.push_back(0);
int maxRes=0;
stack<int> sta;
for (int i=0;i<height.size();i++)
{
int top;
int newRes;
while(!sta.empty()&&height[i]<height[sta.top()])
{
top=sta.top();
sta.pop();
newRes=(sta.empty()?i:(i-sta.top()-1))*height[top];
maxRes=maxRes>newRes?maxRes:newRes;
}
sta.push(i);
}
return maxRes;
}
int maximalRectangle(vector<vector<char> > &matrix)
{
if(matrix.empty())return 0;
int m=matrix.size();
if(matrix[0].empty())return 0;
int n=matrix[0].size();
int maximal=0;
vector<vector<int>> d(m,vector<int> (n));
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(i==0)d[i][j]=matrix[i][j]-'0';
else
{
if(matrix[i][j]=='1')
{
d[i][j]=d[i-1][j]+matrix[i][j]-'0';
}
else
{
d[i][j]=matrix[i][j]-'0';
}
}
}
int tmp=largestRectangleArea(d[i]);
maximal=maximal>tmp?maximal:tmp;
}
return maximal;
}
};