Daily LeetCode 221. Maximal Square

https://leetcode.com/problems/maximal-square/

Medium

问题描述

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example:

Input: 

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

Output: 4

思路及代码：

这一题是从一个二维数组中找出由1构成的最大的正方形的面积，可以通过动态规划的方法来解决，维护一个二维数组dp，dp[i][j]表示以当前点为右下角顶点能够构造的正方形最大边长。

dp数组的第一行和第一列与原数组相同，从第二行开始更新，在遍历过程中，首先判断matrix[i][j]是否为0，若为零，则当前点不能作为正方形的右下顶点，dp[i][j]设置为零；接着从dp[i][j]左边dp[i-1][j]、上边dp[i][j-1]以及斜上方dp[i-1][j-1]中选取最小值加一作为dp[i][j]的值。

拿题中例子来说，输入
$$
1 \quad 0\quad 1 \quad 0\quad 0\
1 \quad 0\quad 1 \quad 1\quad 1\
1 \quad 1\quad 1 \quad 1\quad 1\
1 \quad 0\quad 0 \quad 1\quad 0
$$
dp数组为：
$$
1 \quad 0\quad 1 \quad 0\quad 0\
1 \quad 0\quad 1 \quad 1\quad 1\
1 \quad 1\quad 1 \quad 2\quad 2\
1 \quad 0\quad 0 \quad 1\quad 0
$$
代码如下：

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if len(matrix) == 0: return 0
        dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        res = 0
        for i in range(len(matrix[0])): 
            dp[0][i] = int(matrix[0][i])
            res = max(res, dp[0][i])
        for j in range(len(matrix)): 
            dp[j][0] = int(matrix[j][0])
            res = max(res, dp[j][0])
            
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                if int(matrix[i][j]):
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
                    res = max(dp[i][j], res)

        return res ** 2