最大黑方阵

这个题解使用动态规划的思路解决问题。首先，定义两个矩阵 row 和 col，其中 row[i][j] 表示从 (i, j) 位置向左延伸的连续黑色像素的最大数目，col[i][j] 表示从 (i, j) 位置向上延伸的连续黑色像素的最大数目。然后，对于每个为黑色的像素 (即 matrix[i][j] == 0)，计算以该点为右下角的最大可能的黑色子方阵。为此，获取从该点向左和向上延伸的黑色像素的最小值（因为方阵需要两边长度相等），并验证这一长度是否可以构成一个有效的子方阵。验证方法是检查顶部水平边和左侧垂直边是否同样拥有至少这么长的连续黑色像素。如果找到更大的黑色子方阵，更新结果数组 res。这种方法确保了最终找到的是最大的且最左上角的黑色子方阵。

时间复杂度: O(m*n*min(m, n))

空间复杂度: O(m*n)

class Solution:
    def findSquare(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        row = [[0] * n for _ in range(m)]  # 存储从当前点向左连续黑色像素数
        col = [[0] * n for _ in range(m)]  # 存储从当前点向上连续黑色像素数
        res = [m-1, n-1, float('-inf')]  # 初始化结果为无效值
        # 状态转移
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:  # 仅考虑黑色像素
                    row[i][j] = row[i][j-1] + 1 if j else 1  # 更新左侧连续黑色像素计数
                    col[i][j] = col[i-1][j] + 1 if i else 1  # 更新上方连续黑色像素计数
                    cur_l = min(row[i][j], col[i][j])  # 确定最大可能的方阵边长
                    while cur_l > res[-1]:  # 只有在找到更大的方阵时才进行检查
                        x = i - cur_l + 1
                        y = j - cur_l + 1
                        if row[x][j] >= cur_l and col[i][y] >= cur_l:  # 检查顶部和左侧边界
                            res = [x, y, cur_l]
                            break
                        cur_l -= 1
        return res if res[-1] != float('-inf') else []  # 检查是否有有效方阵