题解 | #最大正方形#

最大正方形

http://www.nowcoder.com/practice/0058c4092cec44c2975e38223f10470e

描述

这是一篇面对初级coder的题解。
知识点：动态规划二维vector使用
难度：二星

题解

给定一个由'0'和'1'组成的2维矩阵，返回该矩阵中最大的由'1'组成的正方形的面积

分析：

与NC109相比，由于寻找的正方形较为规整所以可以动态规划

方法一：暴力求解

遍历数组对于每一个可能是1的点循环扩大正方形面积

扩大面积时可按如下方法遍历保证只遍历一遍：

class Solution {
public:
    int findsquare(vector<vector<char> >& matrix,int i,int j,int l,int w)
    {
        int ans=1;//最小1
        //循环加L型 扩大正方形
        while(1)
        {
            for(int side=0;side<ans+1;side++)//左侧竖列 由上到下
            {
                if(l<=i+ans||w<=j+side||'0'==matrix[i+ans][j+side])
                    return ans;
            }
            for(int side=0;side<ans+1;side++)//下侧横行 由左到右
            {
                if(l<=i+side||w<=j+ans||'0'==matrix[i+side][j+ans])
                    return ans;
            }
            ans++;
        }
        
        return ans;
    }
    int solve(vector<vector<char> >& matrix) {
        int ans=0;//返回答案
        int l=matrix.size() ,w=matrix[0].size();//矩阵长宽
        for(int i=0;i<l;i++)//双重遍历
        {
            for(int j=0;j<w;j++)
            {
                if('1'==matrix[i][j])//=1 是正方形
                {
                int maxsquare=findsquare(matrix,i,j,l,w);//迭代判断最大边长
                if(ans<maxsquare)
                    ans=maxsquare;//当前值大于最大值 记录最大边长
                }
            }
        }
        return ans*ans;//返回面积
    }
};

时间复杂度 $O(mnk^2)$ ：其中 $m$ 和 $n$ 是矩阵的行数和列数。需要遍历整个矩阵寻找每个 1，遍历矩阵的时间复杂度是 $O(mn)$ 。对于每个可能的正方形，最坏情况下，其边长不超过 $m$ 和 $n$ 中的最小值 $k$ ， $k=min(m,n)$ ，需要遍历每个元素判断，故最坏情况时间复杂度 $O(mnk^2)$ ，最好情况即使最大正方形边长为1，时间复杂度 $O(mn)$

空间复杂度O(1)：没有额外使用的空间

运行时间3ms 占用内存396KB

方法二：动态规划

从[1,1]开始遍历进行动态规划

递归公式

matrix[i][j] = min(matrix[i - 1][j], min(matrix[i - 1][j - 1], matrix[i][j - 1])) + 1;

注：这里为了节约内存，直接在原数组上输出，最开始+1相当于是在char上+1 故要最后转化为int

class Solution {
public:
    int solve(vector<vector<char> >& matrix) {
        int ans=0;//返回答案
        int l=matrix.size() ,w=matrix[0].size();//矩阵长宽
        for (int i=1;i<l;i++) 
        {
            for (int j=1;j<=w;j++) 
            {
                if(matrix[i][j]=='1')//符合递归条件
                {
                    //递推公式
                    matrix[i][j] = min(matrix[i - 1][j], min(matrix[i - 1][j - 1], matrix[i][j - 1])) + 1;
                    //记录最大的边长
                    ans = max(ans, (int)matrix[i][j]);
                }
            }
        }
        return (ans-'0')*(ans-'0');//转化为10进制输出
    }
};

运行时间3ms 占用内存384KB

时间复杂度 $O(mn)$ ：其中 $m$ 和 $n$ 是矩阵的行数和列数。需要遍历整个矩阵寻找每个 1

空间复杂度O(1)：直接在原数组上进行操作，没有额外使用的空间。