思路：将矩阵中的最大矩形问题转换成直方图中的最大矩形问题。

1. 从上到下遍历矩阵，以矩阵的每一行作为基线，看成一个直方图，一个n行的矩阵就有n个直方图，分别对这n个直方图求最大面积即可；
2. 用一个heights数组来记录以某一行作为基线的直方图的每根柱子的高度，如果矩阵中某个格子的值为0，那么它所在的柱子的高度为0；如果矩阵中某个格子的值为1，那么它所在的柱子的高度是以上一行作为基线的直方图同一位置的柱子的高度加1；
3. largestRectangleArea方法就是上一题的算法（单调栈）：直方图最大矩形面积。

class Solution {
public:
    int maximalRectangle(vector<string>& matrix) {
        if (matrix.empty()) return 0;

        int maxArea = 0;
        vector<int> heights(matrix[0].size(), 0);

        for (string& row : matrix)
        {
            for (int i = 0; i < row.length(); ++ i)
            {
                if (row[i] == '0') heights[i] = 0;  //当前格子为0，则它所在的柱子高度为0
                else heights[i] ++ ;                //格子为1，则它的高度为上一行同位置高度+1
            }

            //每遍历完一行，就计算以这行为基线的直方图最大面积
            maxArea = max(maxArea, largestRectangleArea(heights));
        }

        return maxArea;
    }

    //使用单调栈求直方图最大矩形面积的方法
    int largestRectangleArea(vector<int>& heights) {
        stack<int> stk;
        stk.push(-1);

        int maxArea = 0;
        for (int i = 0; i < heights.size(); ++ i)
        {
            while (stk.top() != -1 && heights[stk.top()] > heights[i])
            {
                int height = heights[stk.top()];
                stk.pop();
                int width = i - stk.top() - 1;
                maxArea = max(maxArea, height * width);
            }

            stk.push(i);
        }

        while (stk.top() != -1)
        {
            int height = heights[stk.top()];
            stk.pop();
            int width = heights.size() - stk.top() - 1;
            maxArea = max(maxArea, height * width);
        }

        return maxArea;
    }
};