0221：最大正方形（★）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        def cal(H):
            res,sk = 0,[]
            for j,h in enumerate(H+[0]):
                while sk and sk[-1][1]>=h:
                    _,x = sk.pop()
                    i = sk[-1][0] if sk else -1
                    res = max(res,min(j-i-1,x)**2)
                sk.append((j,h))
            return res
        res, H = 0, [0]*len(matrix[0])
        for row in matrix:
            H = [a+1 if b=='1' else 0 for a,b in zip(H,row)]
            res = max(res,cal(H))
        return res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        res, dp = 0, [0]*n  
        for row in matrix:
            new = [0]*n
            for j,x in enumerate(row):
                if x=='1':
                    new[j] = 1 if j==0 else 1+min(dp[j-1],dp[j],new[j-1])
            dp = new
            res = max(res,max(dp))
        return res*res