LeetCode第 85 题：最大矩形(C++)_最大的矩形纸片

85. 最大矩形 - 力扣（LeetCode）

单调栈求矩形面积系列：
LeetCode第 84 题：柱状图中最大的矩形(C++)_zj-CSDN博客
LeetCode第 85 题：最大矩形(C++)_zj-CSDN博客
LeetCode第 221 题：最大正方形(C++)_zj-CSDN博客

和LeetCode第 84 题：柱状图中最大的矩形(C++)_zj-CSDN博客题类似，将每一行都看作一个柱形图：

第一层柱状图的高度["1","0","1","0","0"]，最大面积为1；

第二层柱状图的高度["2","0","2","1","1"]，最大面积为3；

第三层柱状图的高度["3","1","3","2","2"]，最大面积为6；

第四层柱状图的高度["4","0","0","3","0"]，最大面积为4；
1
2
3
4
5
6
7

然后套用84题的计算方法：

class Solution {
public:
    int res;
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.size() == 0 || matrix[0].size() == 0) return 0;
        int row = matrix.size(), col = matrix[0].size();
        vector<int> heights(col);
        for(int i = 0; i < row; ++i){
            for(int j = 0; j < col; ++j){
                if(matrix[i][j] != '0')   heights[j] += 1;
                else heights[j] = 0;
            }
            largestRectangleAera(heights);
        }
        return res;
    }

    void largestRectangleAera(vector<int> heights){
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        stack<int>  stk;
        for(int i = 0; i < heights.size(); ++i){
            while(!stk.empty() && heights[i] < heights[stk.top()]){
                int h = heights[stk.top()];
                stk.pop();
                int w = i - stk.top() - 1;
                res = max(res, h*w);
            }
            stk.push(i);
        }
    }
};
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

但是这样做得效率一般，因为只能使用值传递，如果要想使用引用传递，就需要修改一下计算柱形图的方法，不再使用哨兵：

class Solution {
public:
    int res;
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.size() == 0 || matrix[0].size() == 0) return 0;
        int row = matrix.size(), col = matrix[0].size();
        vector<int> heights(col, 0);
        for(int i = 0; i < row; ++i){
            for(int j = 0; j < col; ++j){
                if(matrix[i][j] == '1') heights[j] += 1;
                else heights[j] = 0;//这儿一定得有else
            }
            largestRectangleArea(heights);//柱形图计算（84题）
        }
        return res;
    }

    void largestRectangleArea(vector<int> &heights){//84题的方法
        stack<int> stk;//单调(递增)栈，存储的是下标
        stk.push(-1);//辅助
        for (int i = 0; i < heights.size(); i++){
            while (stk.top() != -1 && heights[stk.top()] > heights[i]){
                int height = heights[stk.top()];//矩形高
                stk.pop();
                int width = i - stk.top() - 1;
                res = max(res, height*width);
            }
            stk.push(i);
        }
        while(stk.top() != -1){
            int height = heights[stk.top()];
            stk.pop();
            //该下标右边的全部比它大（因为单调性嘛）
            int width = heights.size() - stk.top() - 1; 
            res = max(res, height*width);
        }
    }
};
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

好像效率也没有改进多少。。。