题目链接
给定一个仅包含 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"]]
输出：0

示例 3：
输入：matrix = [["1"]]
输出：1

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

思路

将二维矩阵初始化为 1 的高度矩阵，依次将每行对应的高度数组应用单调栈计算最大面积（参考84. 柱状图中最大的矩形。计算所有行的最大面积即为结果。

代码

class Solution {
public:
    int* order_stack(int heights[], int len, bool reverse) {
        int* res = new int[len];

        int begin = 0;
        int end = len;
        int step = 1;
        int out = -1;
        if (reverse) {
            begin = len - 1;
            end = -1;
            step = -1;
            out = len;
        }

        int *st = new int[len];
        int top = -1;
        for (int i = begin; i != end; i += step) {
            if (top == -1) {
                st[++top] = i;
                res[i] = out;
            } else {
                while(top != -1 && heights[st[top]] >= heights[i]) top --;

                if (top == -1) {
                    res[i] = out;
                } else {
                    res[i] = st[top];
                }
                st[++top] = i;
            }
        }

        return res;
    }

    int solve(int heights[], int len) {
        int *res1 = order_stack(heights, len, false);
        int *res2 = order_stack(heights, len, true);
        int res = 0;
        for (int i = 0; i < len; i ++) {
            res = max(res, heights[i] * (res2[i] - res1[i] - 1));
        }

        return res;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        int height[202][202];
        memset(height, 0, sizeof(height));

        for (int i = 0; i < matrix.size(); i ++) {
            for (int j = 0; j < matrix[0].size(); j ++) {
                if (matrix[i][j] == '0') {
                    height[i][j] = 0;
                } else {
                    if (i > 0) height[i][j] = height[i - 1][j] + 1;
                    else height[i][j] = 1;
                }

                // cout << i << " " << j << " " << height[i][j] << endl;
            }
        }

        int res = 0;
        for (int i = 0; i < matrix.size(); i ++) {
            int cur = solve(height[i], matrix[0].size());
            res = max(res, cur);
        }

        return res;
    }
};