LC

题目

思路

朴素做法首先枚举矩形左上角和右下角坐标，复杂度为$O(n^2) * O(n^2)$，对于每个方案，判断内部是否全为1也是$O(n^2)$的。因此总的复杂度爆炸$O(n^6)$。

当然，判断内部1这一步可以用前缀和来优化掉，但是复杂度依旧是比较恐怖的。

这一题借鉴了LC-84的思路，站在巨人的肩膀上思考。已知可以线性时间内求一堆柱子中的最大面积，如何应用到这个问题中来？

可以考虑按行把大矩阵切割成n份，高度从1到n，对于每一个子矩阵，在切割线上方都会有若干个连续的1，这些连续的1可以看成是柱子。

如何求某个位置上方有几个连续的1呢？这个可以通过递推来求。不妨设某个点的下标为(i, j),用f[i,j]表示这个点上方有多少个连续的1。我们从上到下递推，如果当前位置的值为0，那么f[i,j] = 0；如果值为1，那么f[i,j] = f[i - 1,j] + 1。因此可以$O(n^2)$时间内预处理出每个点上方有多少连续的1。

之后按行枚举整个矩阵，每一行都变成了一个LC-84的模板题。因此总的时间复杂度也是$O(n^2)$的。

代码

class Solution {
public:

    int maxRectangleArea(vector<int>& h) {
        int n = h.size();
        stack<int> stk;
        vector<int> left(n), right(n);

        for(int i = 0; i < n; i++) {
            while(stk.size() && h[stk.top()] >= h[i]) stk.pop();
            if(stk.empty()) left[i] = -1;
            else left[i] = stk.top();
            stk.push(i);
        }

        stk = stack<int>();

        for(int i = n - 1; i >= 0; i--) {
            while(stk.size() && h[stk.top()] >= h[i]) stk.pop();
            if(stk.empty()) right[i] = n;
            else right[i] = stk.top();
            stk.push(i);
        }

        int res = 0;
        for(int i = 0; i < n; i++) {
            res = max(res, h[i] * (right[i] - left[i] - 1));
        }
        return res;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.empty() || matrix[0].empty()) return 0;
        int n = matrix.size(), m = matrix[0].size();

        vector<vector<int>> h(n, vector<int>(m));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(matrix[i][j] == '1'){
                    if(i) h[i][j] = h[i - 1][j] + 1;
                    else h[i][j] = 1;
                }
            }
        }
        int res = 0;
        for(int i = 0; i < n; i++) 
            res = max(res, maxRectangleArea(h[i]));
        return res;
    }
};

拓展

求最大正方形？LC-221

思路

可以考虑DP。f[i,j]表示以[i,j]为右下角的最大正方形的边长。如果matrix[i,j] == 1那么f[i,j] = min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1; 否则f[i,j] = 0。

解释一下递推式： 已知右下角的数为1，那么最大的正方形的大小受限于以matrix[i - 1][j]，matrix[i][j - 1]，matrix[i - 1][j - 1]为右下角的最大正方形的边长。举个例子：

1 1 1 1
0 1 1 1
0 1 1 1
0 1 1 1

（假设下标从1开始）f[4,4] = min(f[3,3], f[4,3], f[3,4]) + 1 = min(2, 3, 2) + 1 = 3

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

f[4,4] = min(f[3,3], f[4,3], f[3,4]) + 1 = min(3, 3, 3) + 1 = 4

求出f数组后遍历一下找最大即可。

时间复杂度$O(n^2)$

代码

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(matrix[i - 1][j - 1] == '1')
                    f[i][j] = min(f[i - 1][j], min(f[i][j - 1], f[i - 1][j - 1])) + 1;
            }
        }
        int res = 0;
        for(int i = 1; i <= n; i++) 
            for(int j = 1; j <= m; j++)
                res = max(res, f[i][j]);
        return res * res;
    }
};