【LeetCode】85. 最大矩形

题目：85. 最大矩形

85. 最大矩形

---

给定一个仅包含0和1 、大小为 rows * 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. 矩阵压缩成数组：逐行叠加，遇到0为0；
2. 求直方图最大矩形：
   1. 设置栈，数组L,R
   2. 遍历元素，
      1. 如果栈顶元素大于当前元素则弹出
      2. 栈空则L[i] = -1
      3. 不空则等于栈顶元素下标
      4. 当前元素入栈
   3. 逆向遍历
      1. 如果栈顶元素大于当前元素则弹出
      2. 栈空则R[i] = n
      3. 不空则等于栈顶元素下标
      4. 当前元素入栈
   4. 最大矩形为当前元素*LR之间距离。

代码

class Solution {
public:
// 1. 矩阵压缩成数组：逐行叠加，遇到0为0；
// 2. 求直方图最大矩形：
// 	1.  设置栈，数组L,R
// 	2. 遍历元素，
// 		1. 如果栈顶元素大于当前元素则弹出
// 		2. 栈空则`L[i] = -1`
// 		3. 不空则等于栈顶元素下标
// 		4. 当前元素入栈
// 	3. 逆向遍历
// 		1. 如果栈顶元素大于当前元素则弹出
// 		2. 栈空则`R[i] = n`
// 		3. 不空则等于栈顶元素下标
// 		4. 当前元素入栈
// 	4. 最大矩形为当前元素*LR之间距离。
    int getMax(vector<int> height) {
        int n = height.size();
        int res = 0;
        vector<int> L(n, 0), R(n, 0);
        stack<int> stack;
        
        for (int i = 0; i < n; i++) {
            while (!stack.empty() && height[stack.top()] >= height[i]) 
                stack.pop();
            if (stack.empty()) L[i] = -1;
            else L[i] = stack.top();
            stack.push(i);
        }
        while (!stack.empty()) stack.pop();

        for (int i = n - 1; i >= 0; i--) {
            while (!stack.empty() && height[stack.top()] >= height[i])
                stack.pop();
            if (stack.empty()) R[i] = n;
            else R[i] = stack.top();
            stack.push(i);
        }

        for (int i = 0; i < n; i++) {
            res = max(res, height[i] * (R[i] - L[i] - 1));
        }
        
        return res;

    }
    int maximalRectangle(vector<vector<char>>& matrix) {
        vector<int> height(matrix[0].size(),0);
        int res = 0;
        for (int i = 0; i < matrix.size(); i++){
            for (int j = 0; j < matrix[0].size(); j++){
                if (matrix[i][j] == '0') height[j] = 0;
                else height[j] += 1;
            }
            res = max(res, getMax(height));
        }
        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