最笨的一种方法，一行行遍历，找matrix[i][j]为1，往右找到连续的max_l个1，就假定最大正方形的边长是max_l，然后从j列i行往下遍历到i+max_l，如果中间有0，说明正方形边长要变短，更新边长max_l。之后遍历matrix[i+1][j+1]到matrix[i+max_l][j+max_l]，中间matrix[m][n]为0需要根据matrix[m][n]到matrix[i][j]较长的部分修正max_l。

import java.util.*;


public class Solution {
    /**
     * 最大正方形
     * @param matrix char字符型二维数组 
     * @return int整型
     */
    public int solve (char[][] matrix) {
        // write code here
        int max_l = 0;
        int max_lr = 0;
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[i].length; j++){
                if (matrix[i][j] == '1'){
                    int k = j + 1;
                    for (k = j + 1; k < matrix[i].length; k++){
                        if (matrix[i][k] == '0'){
                            break;
                        }
                    }
                    max_l = k - j;
                    if (max_l < max_lr){
                        continue;
                    }
                    int l = i + 1;
                    for(l = i + 1; (l < i + max_l) && (l < matrix.length); l++) {
                        if (matrix[l][j] == '0'){
                            break;
                        }
                    }
                    max_l = l - i;
                    if (max_l < max_lr){
                        continue;
                    }
                    for (int m = i + 1; (m < i + max_l) && (m < matrix.length); m++){
                        for(int n = j + 1; (n < j + max_l) && (n < matrix[m].length); n++){
                            if (matrix[m][n] == '0') {
                                max_l = (m - i > n - j) ? m - i : n - j;
                                if (max_l < max_lr){
                                    continue;
                                }
                            }
                        }
                    }
                    if (max_lr < max_l) {
                        max_lr = max_l;
                    }
                }
            }
        }
        return max_lr*max_lr;
    }
}

这个题目有进阶的方法，题目提示了时间空间复杂度都是n^2，方法是动态规划，目前有一点点的思路。

当前思路：

1、如果确定a[i][j]到a[i+n][j+n]都是1，那么在a[i+n+1][j+n+1]时只需要确定a[i+n+1][j]到a[i+n+1][j+n+1]和a[i][j+n+1]到a[i+n+1][j+n+1]是1，就可以确定a[i][j]到a[i+n+1][j+n+1]都是1。不需要重复遍历。

2、确定a[i+n+1][j]到a[i+n+1][j+n+1]是1，如果可以确定a[i+n+1][j]到a[i+n+1][j+n]是1，那么只需要判断a[i+n+1][j+n+1]是否为1。a[i][j+n+1]到a[i+n+1][j+n+1]同理。

3、用数组记录每个点上面连续的1的个数up，左边连续的1的个数left，以及以当前节点为终点的正方形边长edge。a[i][j]为0时，记录为(0,0，0)，否则记录为(a[i-1][j].left+1,a[i][j-1].right+1,edge)，若a[i-1][j-1].edge是0，则a[i][j].edge=1,否则，a[i][j]的edge需要根据情况计算。

情况一：a[i][j].left>edge && a[i][j].right>edge edge=a[i][j].edge+1

情况二：edge=min(a[i][j].left,a[i][j].right)

例如： 最终结果是：

[[1,0,1,0,0], [[(1,1,1),(0,0,0),(1,1,1),(0,0,0),(0,0,0)],

[1,0,1,1,1], [(1,2,1),(0,0,0),(1,2,1),(2,1,1),(3,1,1)],

[1,1,1,1,1], [(1,3,1),(2,1,1),(3,3,1),(4,2,2),(5,2,2)],

[1,0,0,1,0]]， [(1,4,1),(0,0,0),(0,0,0),(1,3,1),(0,0,0)]]

最终边长为edge_max,在循环的过程中，将（left，up）中较小的值比如up较小，且up>edge_max，则edge_max=up

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最大正方形
# @param matrix char字符型二维数组 
# @return int整型
#
class Solution:
    def solve(self , matrix: List[List[str]]) -> int:
        # write code here
        result_mix=[]
        edge_max = 0
        for i in range(len(matrix)):
            r = []
            for j in range(len(matrix[i])):
                obje = {'left':0,'up':0,'edge':0}
                if matrix[i][j] == '0':
                    r.append(obje)
                else:
                    if i == 0 and j == 0:
                        obje = {'left':1,'up':1,'edge':1}
                    elif i == 0 and j > 0:
                        obje = {'left':r[j-1]['left'] + 1,'up':1,'edge':1}
                    elif j == 0 and i > 0:
                        obje = {'left':1,'up':result_mix[i-1][j]['up'] + 1,'edge':1}
                    else:
                        obje = {'left':r[j-1]['left'] + 1,'up':result_mix[i-1][j]['up'] + 1,'edge':result_mix[i-1][j-1]['edge']}
                        if obje['left'] > obje['edge'] and obje['up'] > obje['edge']:
                            obje['edge'] = obje['edge'] + 1
                        else:
                            if obje['left'] > obje['up']:
                                obje['edge'] = obje['up']
                            else:
                                obje['edge'] = obje['left']
                    if obje['edge'] > edge_max:
                        edge_max = obje['edge']
                    r.append(obje)
            result_mix.append(r)
        return edge_max*edge_max

很奇怪，两种方法下面的耗时更长，上面的占用的空间更多