题目的主要信息：

• 给定一个由'0'和'1'组成的2维矩阵，返回该矩阵中最大的由'1'组成的正方形的面积
• 输入的矩阵是字符形式而非数字形式

方法一：动态规划

具体做法：

对于这类区间内找最大某某值的问题，一般采用动态规划。

可以用$dp[i][j]dp[i][j]$表示以$[i,j][i,j]$点处为右下角的正方形的边长，很明显如果这个点本来就是0，则边长就为0，如果这个点是1才可能会有边长。如下图所示，需要需要检查这个点左边、上边、左上角三个点，这三个点可以直接决定以$[i,j][i,j]$点处为右下角的正方形的边长有多长，因为新增的正方形都是在它们三个最小值的基础上增加1，因此转移方程为$dp[i][j]=min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]))+1dp[i][j]\; =\; min(dp[i\; -\; 1][j],\; min(dp[i\; -\; 1][j\; -\; 1],\; dp[i][j\; -\; 1]))\; +\; 1$，然后维护最大边即可。

class Solution {
public:
    int solve(vector<vector<char> >& matrix) {
        int n = matrix.size();
        if(n == 0) //排除空矩阵
            return 0;
        int m = matrix[0].size();
        vector<vector<int> > dp(n + 1, vector<int>(m + 1, 0)); //dp[i][j]表示以i-1,j-1为结尾的正方形的边长
        int maxL = 0; //记录最大的边
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(matrix[i - 1][j - 1] == '1'){ //如果结尾点为1才可能构成正方形
                    dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i][j - 1])) + 1; //选取三种情况的最小值加1
                    maxL = max(maxL, dp[i][j]); //维护最大边
                }
            }
        }
        return maxL * maxL; //返回面积
    }
};

复杂度分析：

• 时间复杂度：$O(nm)O(nm)$，其中$mm$、$nn$为输入矩阵的边长，遍历整个矩阵
• 空间复杂度：$O(nm)O(nm)$，辅助数组dp的大小

方法二：动态规划空间优化

具体做法：

因为矩阵的长宽不会超过20，因此可以直接将编程添加在原始矩阵上，比如如果以$[i,j][i,j]$为右下角的正方形边长为5，则可以记为'5'，减去字符'0'即可获取边长，因为长不会超过20，因此不会超过ASCⅡ的表示范围，每次可以通过对三个方向相邻的元素减去字符'0'即可获取三个边长，然后比较获取最小值，再加上字符'1'记录回原矩阵$[i,j][i,j]$的位置，这样就省去了dp数组的空间。

class Solution {
public:
    int solve(vector<vector<char> >& matrix) {
        int n = matrix.size();
        if(n == 0) //排除空矩阵
            return 0;
        int m = matrix[0].size();
        int x00, x01, x10;
        int maxL = 0; //记录最大的边
        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                if(matrix[i][j] == '0') //如果结尾点不为0才可能构成正方形
                    continue;
                x00 = matrix[i - 1][j - 1] - '0'; //获取三个方向边长
                x01 = matrix[i - 1][j] - '0';
                x10 = matrix[i][j - 1] - '0';
                if(x00 && x01 && x10)
                    matrix[i][j] = min(x00, min(x01, x10)) + '1'; //取最小值加1，这里是字符1
                maxL = max(maxL, matrix[i][j] - '0'); //维护最大值
            }
        }
        return maxL * maxL; //返回面积
    }
};

复杂度分析：

• 时间复杂度：$O(nm)O(nm)$，其中$mm$、$nn$为输入矩阵的边长，遍历整个矩阵
• 空间复杂度：$O(1)O(1)$，无额外空间