给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例:
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6
思路：
每一行计算高度，转换成 84. 柱状图中最大的矩形的问题。实现代码如下所示。
class Solution {
public:
int rows,cols;
int maximalRectangle(vector<vector<char>>& matrix) {
if(!matrix.size() || !matrix[0].size())
{
return 0;
}
int res=0;
rows=matrix.size();
cols=matrix[0].size();
vector<vector<int>> heights;
heights=vector<vector<int>>(rows,vector<int>(cols,0));
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
if(matrix[i][j]=='1')
{
heights[i][j]=i==0?1:(heights[i-1][j]+1);
}
}
res=max(res,largestRectangleArea(heights[i]));
}
return res;
}
int largestRectangleArea(vector<int> heights)
{
stack<int> st;
int res=0;
heights.push_back(0);
for(int i=0;i<heights.size();i++)
{
if(st.empty() || heights[st.top()]<heights[i])
{
st.push(i);
}
else
{
int curr=st.top();
st.pop();
res=max(res,heights[curr]*(st.empty()?i:i-1-st.top()));
i--;
}
}
return res;
}
};
