leetcode-221-最大正方形

发表于 阅读次数： 本文字数： 655 阅读时长 ≈ 1 分钟
简介：leetcode-221-最大正方形

题目

https://leetcode.cn/problems/maximal-square/submissions/535259143/?envType=study-plan-v2&envId=dynamic-programming

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m,n = len(matrix), len(matrix[0])
        lst = [[0 for j in range(n)] for i in range(m)]

        for i in range(m):
            lst[i][0] = int(matrix[i][0])
        for i in range(n):
            lst[0][i] = int(matrix[0][i])
        
        for i in range(1,m):
            for j in range(1,n):
                a,b,c = lst[i-1][j],lst[i][j-1],lst[i-1][j-1]
                if int(matrix[i][j]) == 0:
                    lst[i][j] = 0
                elif min(a,b,c) == 0:
                    lst[i][j] = int(matrix[i][j])
                elif min(a,b,c) < max(a,b,c):
                    lst[i][j] = min(a,b,c)+1
                else:
                    lst[i][j] = a+1
        # print(lst)

        bian = max(map(max,lst))
        return bian*bian