LeetCode 221. 最大正方形

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

输入: 

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

输出: 4

思路

动态规划，设dp[i][j]为以matrix[i][j]为右下角的正方形的最大边长，若matrix[i][j]==1,看看这个正方形还能不能扩展，dp[i][j]=1+min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1])) 若matrix[i][j]==0,肯定不是正方形,dp[i][j]=0

理解

画图更直观一些

代码

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