221. Maximal Square

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

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

Thoughts

01矩阵返回内部由1组成的最大方阵的大小。argmax + 格子 => DP。dp[i][j]表示在(i, j)处最大方阵边长是多少，当它是1时，它由左，上和斜能构成的最大方阵拼接而成，且大小受制于邻居中最小的。总结果是argmax_(i, j)，所有子结果中最优的。

Code

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

Analysis

Errors:

1. m == 0 || matrix[0] == null没考虑

2. return pow(2, max)

时间复杂度O(mn).