0221._maximal_square.md

221. Maximal Square

难度: Medium

刷题内容

原题连接

• 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

解题方案

思路 1 - 时间复杂度: O(row * col)- 空间复杂度: O(row * col)******

dp[i][j]代表以matrix[i][j]为右下角的正方形的最大长度

状态方程dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1，但是必须要满足dp[i][j] == 1，因为右下角也必须为1啊

原本的matrix                     DP

1 0 1 0 0                     1 0 1 0 0
1 0 1 1 1            →        1 0 1 1 1
1 1 1 1 1                     1 1 1 2 2
1 0 0 1 0                     1 0 0 1 0

beats 48.42%

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        row = len(matrix)
        col = len(matrix[0]) if row else 0
        dp = [[int(matrix[i][j]) for j in range(col)] for i in range(row)]

        for i in range(1, row):
            for j in range(1, col):
                if dp[i][j] == 1:
                    dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1

        max_len = 0
        for i in range(row):
            for j in range(col):
                max_len = max(max_len, dp[i][j])
        return max_len * max_len