leetcode 85.最大矩形 单调栈应用_leetcode85

题目描述

最大矩形
给定一个仅包含 $0$ 和 $1$ 、大小为 $rows\times cols$ 的二维二进制矩阵，找出只包含 $1$ 的最大矩形，并返回其面积。

思路

这题要从柱状图中最大的矩形中得到思路

• 从矩阵中找出直方图，那么就能通过计算直方图中的最大矩形面积来计算矩阵中的最大矩形面积
• 将矩阵中上下相邻的值为1的格子看成直方图中的柱子

以如下的矩阵为例：

可以按行为基线，划分成四个84题中的柱状图。

这样，求矩阵中面积最大的全1矩形，即是求这所有转化而来的柱状图中最大的矩形面积。

思路：

1. 把矩阵的每行看作柱状图，先由原矩阵得到表示柱状图的序列
2. 对每行调用84题中的函数，求答案的最大值即可

代码

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.size()==0||matrix[0].size()==0) return 0;
        int num=0;
        for(int i=0;i<matrix.size();i++)
            for(int j=0;j<matrix[0].size();j++)
                if(matrix[i][j]=='1')
                    num++;
        if(num==0) return 0;
        //以上为特殊值判断处理
        //一定要给二维的vector开辟空间，不然后面不能直接用下标访问
        vector<vector<int> > count(matrix.size());
        for(int i=0;i<matrix.size();i++)
            count[i].resize(matrix[0].size());
        //把矩阵的每行看作柱状图，先由原矩阵得到表示柱状图的序列
        for(int i=0;i<matrix.size();i++)
            for(int j=0;j<matrix[0].size();j++)
                if(i==0)
                    count[i][j]=matrix[i][j]-'0';
                else
                {
                    if(matrix[i][j]=='1')
                    {
                        if(matrix[i-1][j]=='1')
                            count[i][j]=count[i-1][j]+1;
                        else
                            count[i][j]=1;
                    } 
                    else    
                        count[i][j]=0;
                }
     //调用84题的函数，求最大值
        int res=-1;
        for(int i=0;i<matrix.size();i++)
            res=max(res,largestRectangleArea(count[i]));
        return res;
    }
    int largestRectangleArea(vector<int>& heights) {
        vector<int> left,right;

        stack<pair<int,int>> s;
        for(int i=0;i<heights.size();i++)
        {
            while(!s.empty()&&s.top().second>=heights[i])
                s.pop();
            if(s.empty())
                left.push_back(-1);
            else
                left.push_back(s.top().first);
            s.push({i,heights[i]});
        }

        while(!s.empty()) s.pop();
        for(int i=heights.size()-1;i>=0;i--)
        {
            while(!s.empty()&&s.top().second>=heights[i])
                s.pop();
            if(s.empty())
                right.push_back(heights.size());
            else
                right.push_back(s.top().first);
            s.push({i,heights[i]});
        }
        reverse(right.begin(),right.end());

        int res=0;
        for(int i=0;i<heights.size();i++)
            res=max(res,(right[i]-left[i]-1)*heights[i]);
        return res;
    }
};
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72