目录

0221:最大正方形(★)

力扣第 221 题

题目

在一个由 '0''1' 组成的二维矩阵内,找到只包含 '1' 的最大正方形,并返回其面积。

示例 1:

输入:matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出:4

示例 2:

输入:matrix = [["0","1"],["1","0"]]
输出:1

示例 3:

输入:matrix = [["0"]]
输出:0

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j]'0''1'

相似问题:

分析

#1

本题是 0085 的子问题,修改一下即可。

 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

194 ms

#2

还可以直接用 dp:

  • 令 dp[i][j] 代表以 (i,j) 为右下顶点的最大正方形的边长,当 matrix[i][j] == ‘1’ 时:

$$dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])$$

  • 用反证法可以证明
  • 可以用滚动数组优化空间

解答

 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

113 ms