2022秋招备战！每天写至少一篇Leetcode里Hard难度题目的题解

85. 最大矩形

给定一个仅包含 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
• 1 <= row, cols <= 200
• matrix[i][j] 为 '0' 或 '1'

方法一 沿用求直方图最大矩形的单调栈做法

根据 84题 的解法，我们可以直接套用之前的代码。

对矩形内逐行分析。建立m个（行数）个heights数组，记得不要传引用，如果你和我一样修改了heights数组。

从第一行开始遍历，生成我们需要的heights数组。

如果当前的值为1，那么更新我们heights数组为heights[i]+1

如果当前的值为0， 那么不管是当前还是再往下，都不可能用到本格作为矩形的一部分，就直接清0。其实是一个递归的dp思想。

$dp[i][j] = matrix[i][j] == 1 ? dp[i-1][j] + 1 : 0$

class Solution {
public:
    int largestRectangleArea(vector<int> heights) {
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        int n = heights.size();
        stack<int> s;
        int res = 0;
        for (int i = 0; i < n; i++) {
            while(!s.empty() && heights[i] < heights[s.top()]) {
                int topHeight = heights[s.top()];
                s.pop();
                int curArea = (i - s.top() - 1) * topHeight;
                res = max(res, curArea);
            }
            s.push(i);
        }
        return res;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int res = 0;
        vector<int> heights(n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    heights[j]++;
                } else heights[j] = 0;
            }
            res = max (largestRectangleArea(heights), res);    
        }

        return res;
    }
};