leetcode85：最大矩形

题目链接

leetcode

题目描述

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

C++ 代码

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

/*
    单调栈

    1.将柱状图中最大的矩形扩展到二维。
    2.一行行考虑，一行内所有柱形条的高度是当前位置(i, j)往上延伸的最大高度。
    3.套用柱状图中最大的矩形问题的单调栈算法。

    时间复杂度：O(mn)
        枚举每一行的时间复杂度是 O(m)，行内单调栈的时间复杂度是 O(n)，故总时间复杂度为 O(mn)。
    空间复杂度：O(mn)
        二维数组需要空间为 O(m*n)，单调栈需要空间为 O(n)。
*/
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) {
            return 0;
        }

        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> h(m, vector<int>(n));

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    h[i][j] = (i == 0 ? 0 : h[i-1][j]) + 1;
                }
            }
        }

        int res = 0;
        for (int i = 0; i < m; i++) {
            // leetcode84. largestRectangleArea
            vector<int>& heights = h[i];
            heights.push_back(-1); // 在数组末尾添加高度-1，使栈中所有数字在最后出栈
            
            stack<int> stk;
            int area = 0;
            for (int j = 0; j <= n; j++) {
                while (!stk.empty() && (heights[j] <= heights[stk.top()])) {
                    int index = stk.top(); stk.pop();

                    if (stk.empty()) {
                        area = max(area, heights[index]*j);
                    } else {
                        area = max(area, heights[index] * (j-stk.top()-1));
                    }
                }
                stk.push(j);
            }
            res = max(res, area);
        }

        return res;
    }
};

/*
    思路同上，优化空间

    时间复杂度：O(mn)
    空间复杂度：O(n)
*/
class Solution_2 {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) {
            return 0;
        }

        int m = matrix.size(), n = matrix[0].size();
        vector<int> h(n+1, 0);
        h[n] = -1;
        int res = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                h[j] = (matrix[i][j] == '0' ? 0 : h[j] + 1);
            }

            stack<int> stk;
            for (int j = 0; j <= n; j++) {
                while (!stk.empty() && h[j] < h[stk.top()]) {
                    int index = stk.top(); stk.pop();
                    if (stk.empty()) {
                        res = max(res, h[index]*j);
                    } else {
                        res = max(res, h[index] * (j-stk.top()-1));
                    }
                }
                stk.push(j);
            }
        }

        return res;
    }
};

// 辅助函数：打印二维数组
void printArray(const vector<vector<char>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << "\"" << nums[i][j] << "\"";
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<vector<char>>> matrix_cases = {
        {
            {'1', '0', '1', '0', '0'},
            {'1', '0', '1', '1', '1'},
            {'1', '1', '1', '1', '1'},
            {'1', '0', '0', '1', '0'}
        },
        {
            {'0'}
        },
        {
            {'1'}
        }
    };

    for (int i = 0; i < matrix_cases.size(); i++) {
        auto& matrix = matrix_cases[i];
        int result = solution.maximalRectangle(matrix);
        
        cout << "Input: matrix = ";
        printArray(matrix);
        cout << endl;
        cout << "Output: " << result << endl;
    }

    return 0;
}
#leetcode
leetcode85：最大矩形
https://lcf163.github.io/2023/12/03/leetcode85：最大矩形/
作者
乘风的小站
发布于
2023年12月3日
许可协议