Leetcode.85 最大矩形_leetcode85

题目链接

Leetcode.85 最大矩形 hard

题目描述

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

解法：单调栈

如果把每一列的 1 看作是一个柱子的话，我们只需要对于每一层都求一下它的最大矩形面积，最终对于每一层的最大面积再求一个最大值，就能得到我们的答案 $ans$。

每一层都求一下它的最大矩形面积，我们直接使用上一题的代码：Leetcode.84 柱状图中最大的矩形

时间复杂度： $O(m\times n)$

c++代码：

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& g) {
        int m = g.size() , n = g[0].size();
        int ans = 0;
        //每一层的柱状图 ， n + 2 是因为首尾分别要插入一个0
        vector<int> heights(n + 2);


        for(int i = 0;i < m;i++){
            //类加每一层的柱状图的高度
            for(int j = 0;j < n;j++){
                if(g[i][j] == '0') heights[j + 1] = 0;
                else heights[j + 1]++;
            }
            //计算每一层柱状图的最大矩形面积
            stack<int> stk;
            for(int j = 0;j < n + 2;j++){
                while(!stk.empty() && heights[stk.top()] > heights[j]){
                    int h = heights[stk.top()];
                    stk.pop();
                    ans = max(ans , (j - stk.top() - 1) * h);
                }
                stk.push(j);
            }
            
        }

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31