221. 最大正方形

题目链接：https://leetcode.cn/problems/maximal-square/
难度：中等

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

题解

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        # r[i][j]代表以matrix[i-1][j-1]为右下角的最大正方形。
        r = [[0] * (n+1) for _ in range(m+1)]
        ret = 0
        for i in range(1, m+1):
            for j in range(1, n+1):
                if matrix[i-1][j-1] == '1':
                    r[i][j] = min(r[i-1][j], r[i][j-1], r[i-1][j-1]) + 1
                    ret = max(ret, r[i][j])
        return ret * ret