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

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

示例 2：

输入：matrix = []
输出：0

示例 3：

输入：matrix = [["0"]]
输出：0

示例 4：

输入：matrix = [["1"]]
输出：1

示例 5：

输入：matrix = [["0","0"]]
输出：0

提示：

• rows == matrix.length
• cols == matrix[0].length
• 0 <= row, cols <= 200
• matrix[i][j] 为 '0' 或 '1'

解答

可以看作是84. 柱状图中最大的矩形的扩展，将矩阵逐行统计元素1的高度，再复用84题中的代码求最大矩形面积：

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.size() == 0 || matrix[0].size() == 0)
            return 0;
        vector<int> heights(matrix[0].size(), 0);
        int result = 0;
        for(const auto& row : matrix){
            for(int i = 0; i < row.size(); i++ ){
                if(row[i] - '0' == 1)
                    heights[i] += (row[i] - '0');
                else
                     heights[i]  = 0;
            }
            result = max(result, largestRectangleArea(heights));
        }
        return result;
    }
    int largestRectangleArea(vector<int>& heights) {
    	// 开头末尾添加0
        vector<int> temp(heights.size() + 2, 0);
        copy(heights.begin(), heights.end(), temp.begin() + 1);

        int result = 0;
        stack<int> s;
        for(int i = 0; i < temp.size(); i++){
            while(!s.empty() && temp[s.top()] > temp[i]){
                int height = temp[s.top()];
                s.pop();
                int weight = i - s.top() - 1;
                result = max(result, height * weight);
            }
            s.push(i);
        }
        return result;
    }
};