85.最大矩形

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例:

输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-rectangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

完整代码

基本思想
动态规划+84.求柱状图中的最大矩形的栈思想

• 动态规划
  将每一行看成一个整体，利用动态规划的思想，需要求出当前行中的每一列中连续1的个数（特别注意：一定要将当前行考虑在内）
  如何求该列中连续1的个数？
  在这里并不是真正意义上的连续1的个数，而是包括当前行的那个值向上面的行延伸的最大值。举例：[[1],[1],[0],[1]]这一列连续1的个数是2，当这里考虑到最后一行，连续1的个数是1，也就是最后一行的1
  参考下图：leetcode
  

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.size() == 0)
            return 0;
        int res = 0;
        vector<int> cell(matrix[0].size(),0);//当前行对应的这一列的连续1的个数
        for(int i = 0; i < matrix.size(); ++i){            
            for(int j = 0; j < matrix[0].size(); ++j){
                if(matrix[i][j] == '1')
                    ++cell[j];
                else
                    cell[j] = 0;
            }
            int cur = max_Rec(cell);
            //cout << cur << endl;
            if(cur > res)
                res = cur;
        }
        
        return res;
    }
private:
    int max_Rec(vector<int> nums){
        // for(auto a:nums)
        //     cout<<a;        
        int res = 0;
        stack<int> st;//存放下标
        st.push(-1);//初始为-1
        nums.push_back(0);//
        for(int i = 0; i < nums.size(); ++i){
            while(st.top() != -1 && nums[i] < nums[st.top()]){
                int cur_height = st.top();
                st.pop();
                int cur_s = nums[cur_height] * (i - st.top() - 1);
                if(cur_s > res)
                    res = cur_s;
            }
            st.push(i);
        }
        return res;
    }
};