题目描述

在一个只包含0和1的二维矩阵中，找到最大的正方形，使得正方形只包含1，返回正方形的面积。

样例

输入：二维01矩阵，如
[
    [1 0 1 0 0],
    [1 0 1 1 1],
    [1 1 1 1 1],
    [1 0 0 1 0]
]
输出：4
解释：可以看到最大的只包含1的正方形面积为4

算法

(枚举) $O(n^3)$

要想找到内部全是1的正方形，一个比较直接的想法就是正方形内部数字之和等于正方形边长的平方，这样通过枚举矩阵内所有的正方形就可以得到答案。而求正方形的和可以通过建立累计数组的方法来提高效率。累计数组sum[i][j]表示从矩阵matrix[0][0]到matrix[i][j]的长方形的和，那么从i1, j1到i2, j2的长方形的内部数字和=sum[i][j]-sum[i-1][j]-sum[i][j-1]+sum[i-1][j-1]。

时间复杂度分析：遍历所有的正方形需要$O(n^3)$

C++ 代码

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.size()==0)
            return 0;
        if(matrix[0].size()==0)
            return 0;
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int> > sum(m+1, vector<int>(n+1, 0));//累计和数组
        sum[1][1] = matrix[0][0] - '0';
        for(int i = 2;i<=m;i++){
            sum[i][1] = sum[i-1][1]+matrix[i-1][0] - '0';
        }
        for(int j = 2;j<=n;j++){
            sum[1][j] = sum[1][j-1] + matrix[0][j-1] - '0';
        }
        for(int i = 2;i<=m;i++){
            for(int j = 2;j<=n;j++){
                sum[i][j] = sum[i-1][j]+sum[i][j-1] - sum[i-1][j-1] + matrix[i-1][j-1]-'0';
            }
        }
        int len = min(m, n);
        for(int l = len;l>=1;l--){//l枚举正方形边长
            for(int i = 0;i+l<=m;i++){
                for(int j =0;j+l<=n;j++){
                    int p1 = i;//正方形左上角
                    int q1 = j;
                    int p2 = i+l;//正方形右下角
                    int q2 = j+l;
                    if((sum[p2][q2]-sum[p1][q2]-sum[p2][q1]+sum[p1][q1])==l*l)
                        return l*l;//如果正方形内部和==正方形面积 则返回
                }
            }
        }
        return 0;
    }
};

算法2

(动态规划) $O(n^2)$

其实这道题可以是一个动态规划问题，用dp[i][j]记录到达(i, j)位置所能组成的最大正方形的边长。
我们首先来考虑边界情况，也就是当i或j为0的情况，那么在首行或者首列中，必定有一个方向长度为1，那么就无法组成长度超过1的正方形，最多能组成长度为1的正方形，条件是当前位置为1。
而对于递推公式，对于任意一点dp[i][j]，由于该点是正方形的右下角，所以该点的右边，下边，右下边都不用考虑，关心的就是左边，上边，和左上边，只有当前(i, j)位置为1，dp[i][j]才有可能大于0，否则dp[i][j]一定为0。当(i, j)位置为1，此时要看dp[i-1][j-1], dp[i][j-1]，和dp[i-1][j]这三个位置，我们找其中最小的值，并加上1，就是dp[i][j]的当前值了，这个并不难想，毕竟不能有0存在，所以只能取交集，最后再用dp[i][j]的值来更新结果res的值即可。

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

C++ 代码

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