跳转至

85 最大矩形

https://leetcode.cn/problems/maximal-rectangle/

若matrix[i][j] == ‘1’,那么以该点为矩形的右下角

  • 记left[i][j]为第i行第j列元素左边连续1的个数(包括第i行第j列)
  • 那么矩形可以转换为若干个柱形,left[i][j]为柱形的高度,题目就变成了84 求柱状图最大的柱形
  • 宽度为k - i + 1,k为第i行前的第k行

换一下坐标轴,宽度就是代码中的高度,高度就是代码中的宽度

解法一:暴力枚举点

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        vector<vector<int>> left(n,vector<int>(m, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == '1') {
                    left[i][j] = (j == 0 ? 0: left[i][j - 1]) + 1;
                }
            }
        }
        int ans = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(matrix[i][j] == '1'){
                    int w = left[i][j];
                    // 这里area初始化为w, 因为假设matrix[k][j]都为'0', 宽度至少为1
                    int area = w;
                    for(int k = i - 1; k >= 0; k--){
                        w = min(w, left[k][j]);
                        area = max(area, (i - k + 1) * w);
                    }
                    ans = max(ans, area);
                }
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度:\(O(m^2n)\),其中 m 和 n 分别是矩阵的行数和列数。计算 left 矩阵需要 O(mn) 的时间。随后对于矩阵的每个点,需要 O(m) 的时间枚举高度。故总的时间复杂度为$ O(mn)+O(mn)⋅O(m)=O(m^2n)$。

空间复杂度:\(O(mn)\),其中 m 和 n 分别是矩阵的行数和列数。我们分配了一个与给定矩阵等大的数组,用于存储每个元素的左边连续 1 的数量。

解法二:单调栈

同84 一样,需要求出柱形图最小的高度(代码中为宽度)

与84不同之处在于,本题可以拆分为m列 柱形图,将84题的代码处理m次即可

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        vector<vector<int>> left(n, vector<int>(m, 0));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(matrix[i][j] == '1')
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
            }
        }
        int ans = 0;
        int len = n + 2;
        // 枚举每一列
        for(int j = 0; j < m; j++){
            stack<int> stk;
            int area = 0;        
            vector<int> ll(len);
            ll[0] = 0;
            ll[len - 1] = 0;
            // 初始化别弄反了,是left[k - 1][j],不是left[j][k - 1]
            for(int k = 1; k < len - 1; k++)
                ll[k] = left[k - 1][j];
            for(int i = 0; i < len; i++){
                while(!stk.empty() && ll[i] < ll[stk.top()]){
                    int idx = stk.top();
                    stk.pop();
                    int w = i - stk.top() - 1;
                    area = max(area, w * ll[idx]);
                }
                stk.push(i);
            }
            ans = max(ans, area);
        }
        return ans;
    }
};

复杂度分析

时间复杂度:O(mn),其中 m 和 n 分别是矩阵的行数和列数。计算 left 矩阵需要 O(mn) 的时间;对每一列应用柱状图算法需要 O(m) 的时间,一共需要 O(mn) 的时间。

空间复杂度:O(mn),其中 m 和 n 分别是矩阵的行数和列数。我们分配了一个与给定矩阵等大的数组,用于存储每个元素的左边连续 1 的数量。