给定一个仅包含 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;
    }
};