221. Maximal Square

problem description

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

Input: 

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

Output: 4

algorithm thought

第一次做这个题的时候，直接暴力解题，得到最大的正方形。感觉多了很多重复计算。后来知道这里可以用动态规划。

将计算正方形的面积首先转化为计算正方形的边长，边长求出来了，面积自然不在话下。这里用二维数组中一个点代表一个正方形，二维数组的值代表边长。这个点是正方形的右下角。

这样如果当前点为1，那么当前点代表的正方形边长就取决于他上面左边和左上正方形的边长了。

上面那个正方形代表了右侧边的最大值，左边正方形的长度代表了下侧边的最大值。左上正方形代表了左上角点的最大值。他们的最小值就是当前正方形的边长。这样就能用动态规划的方式，一次遍历二维数组得到结果

code

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

algorithm analysis

这个算法遍历二维数组，遍历过程中每次操作时间复杂度是O(1)，最后时间复杂度O(n²)