Maximal Rectangle
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
使用dpHeight[]数组来记录到第i行为止，第j个位置垂直连续包含多少个1（包括matrxi[i][j]）。如：
1 0 1 1 0
1 1 0 1 0
0 1 1 1 1
有如下结果：
第1行： dpHeight[] = {1, 0, 1, 1, 0}
第2行： dpHeight[] = {2, 1, 0, 2, 0}
第3行： dpHeight[] = {0, 2, 1, 3, 0}
对每个dpHeight求最大矩形面积，利用Largest Rectangle in Histogram里面的求解方法即可
class Solution {
public:
int maximalRectangle(vector<vector<char> > &matrix) {
int m=matrix.size();
if(m==) return ;
int n=matrix[].size();
vector<int> dpHeight(n,);
int result=;
for(int i=;i<m;i++)
{
for(int j=;j<n;j++)
{
if(matrix[i][j]=='') dpHeight[j]++;
else dpHeight[j]=;
}
int tmp=lineMaximalRectangle(dpHeight);
if(tmp>result) result=tmp;
}
return result;
}
struct Node
{
int index;
int height;
Node(int i,int h):index(i),height(h){};
};
int lineMaximalRectangle(vector<int> &dpHeight)
{
int len=dpHeight.size();
if(len==) return ;
stack<Node> stk;
Node n(,dpHeight[]);
stk.push(n);
int result=;
for(int i=;i<len;i++)
{
int height=dpHeight[i];
if(height>=stk.top().height)
{
stk.push(Node(i,height));
}
else
{
int nodeIndex=i;
while(!stk.empty()&&height<stk.top().height)
{
int tmp=(i-stk.top().index)*stk.top().height;
if(tmp>result) result=tmp;
nodeIndex=stk.top().index;
stk.pop();
}
stk.push(Node(nodeIndex,height));
}
}
while(!stk.empty())
{
int index=stk.top().index;
int height=stk.top().height;
int tmp=(len-index)*height;
if(tmp>result) result=tmp;
stk.pop();
}
return result;
}
};