描述

这是一篇面对初级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;//返回面积
    }
};
时间复杂度：其中 和是矩阵的行数和列数。需要遍历整个矩阵寻找每个 1，遍历矩阵的时间复杂度是 。对于每个可能的正方形，最坏情况下，其边长不超过 和  中的最小值，，需要遍历每个元素判断，故最坏情况时间复杂度，最好情况即使最大正方形边长为1，时间复杂度
空间复杂度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
时间复杂度：其中  和是矩阵的行数和列数。需要遍历整个矩阵寻找每个 1
空间复杂度O(1)：直接在原数组上进行操作，没有额外使用的空间。

总结

有递推性质的问题可以考虑动态规划
原数组不要的时候可以直接在原数组上输出