class Solution {
public:
int method(vector<int> h)//求柱状图中最大的矩形
{
int n=h.size();
vector<int> l=vector<int> (n),r=l;
stack<int> st;
//预处理l，r数组
for(int i=0;i<n;i++)
{
while(st.size()&&h[st.top()]>=h[i]) st.pop();
if(st.size()) l[i]=st.top();
else l[i]=-1; //没有比h[i]小的数
st.push(i);
}
st=stack<int> ();
for(int i=n-1;i>=0;i--)
{
while(st.size()&&h[st.top()]>=h[i]) st.pop();
if(st.size()) r[i]=st.top();
else r[i]=n; //没有比h[i]小的数
st.push(i);
}
//计算最大矩形面积
int res=0;
for(int i=0;i<n;i++)
res=max(res,h[i]*(r[i]-l[i]-1));
return res;
}
int maximalRectangle(vector<vector<char>>& matrix) {
int n=matrix.size(),m=matrix[0].size();
vector<vector<int> > h=vector<vector<int> > (n,vector<int> (m));
//初始化h[i][j],表示matrix[i][j]在j列从i行往上数，1的个数
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if('0'==matrix[i][j]) h[i][j]=0;
else if(i) h[i][j]=1+h[i-1][j];
else h[i][j]=1;
}
//枚举每一行
int res=0;
for(int i=0;i<n;i++)
res=max(res,method(h[i]));
return res;
}
};