题目内容

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

提示

1、rows == matrix.length
2、cols == matrix[0].length
3、0 <= row, cols <= 200
4、matrix[i][j] 为 ‘0’ 或 ‘1’

题解

本题是上一题的变种，但是思路不变。在本题中，可以将整个矩阵中的每一行当做柱状图的x轴，那么问题就转化为了求x轴上方柱状图可以组成的最大矩形的面积，见下图。

在具体做法上，针对如何求出每个柱子的高度上，可以采用递归的思路，即h(i,j)代表当前格子网上的柱子的最大高度，那么有：若当前格子上的数字为0，那么h(i,j) = 0；若当前格子上的数字为1，那么h(i,j) = 1 + h(i-1,j)。

具体，请看代码。

代码

class Solution {
public:
    int largestRectangleArea(vector<int>& h) {
        int n = h.size();
        vector<int> left(n), right(n);
        stack<int> stk;

        for (int i = 0; i < n; i ++ ) {
            while (stk.size() && h[stk.top()] >= h[i]) stk.pop();
            if (stk.empty()) left[i] = -1;
            else left[i] = stk.top();
            stk.push(i);
        }

        stk = stack<int>();
        for (int i = n - 1; i >= 0; i -- ) {
            while (stk.size() && h[stk.top()] >= h[i]) stk.pop();
            if (stk.empty()) right[i] = n;
            else right[i] = stk.top();
            stk.push(i);
        }

        int res = 0;
        for (int i = 0; i < n; i ++ ) {
            res = max(res, h[i] * (right[i] - left[i] - 1));
        }

        return res;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        //思路就是固定底边，然后看从底边网上是否存在连续的1，如果存在记录长度，然后从中找出最大的矩形的面积，最后求出矩形面积的全局最大值。另外有递推公式：h(i,j) = 1 + h(i - 1,j)
        if(matrix.empty() || matrix[0].empty()) return 0;
        //n表示高度，m表示宽度
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<int>> h(n,vector<int>(m));//设置状态方程
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                if(matrix[i][j] == '1'){
                    if(i) h[i][j] = 1 + h[i - 1][j];//如果i大于0，那么就是上述递推公式
                    else h[i][j] = 1;
                }
        int res = 0;
        for(int i = 0; i < n; i++) res = max(res, largestRectangleArea(h[i]));

        return res;
    }
};