0221：最大正方形（★）

2015-08-09 约 344 字预计阅读 1 分钟次阅读

力扣第 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

目录

0221：最大正方形（★）

题目

分析

#1

#2

解答