题目

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

示例:

输入:

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

输出: 4

解题思路

使用动态规划的思想，对于matrix[i][j]对应的dp[i][j]表示i，j作为正方形的右下角的正方形边长，当dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]存在零的时候，dp[i][j]为matrix[i][j]的值，当都不为零时，dp[i][j] 为三个值中最小的值+1。

代码

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.size() == 0) return 0;
        int dp[matrix.size()][matrix[0].size()] = {0};
        int maxRec = 0;
        //初始化
        for(int i=0; i < matrix.size(); i++){
            dp[i][0] = matrix[i][0] - '0';
            maxRec = max(matrix[i][0] - '0', maxRec);
        }
        
        for(int j = 0; j < matrix[0].size();j++){
            dp[0][j] = matrix[0][j] - '0';
            maxRec = max(matrix[0][j]-'0', maxRec);
        }
        
         //开始查找
        for(int i=1; i < matrix.size(); i++){
            for(int j=1; j < matrix[0].size(); j++){
                if(matrix[i][j] == '1'){
                    dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                    maxRec = max(dp[i][j], maxRec);
                }else{
                    dp[i][j] = 0;
                }
            }
        }
        return maxRec*maxRec;
    }
};