Leetcode 221.最大正方形

Posted on |

221. 最大正方形

题目

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

1
2
3
4
5
6
7
8
9
10
示例:

输入:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

方法

方法1：动态规划

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
26
27
28
29
30
31
class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        dp[i][j]表示以matrix中第i行第j列为右下角所能构成的最大正方形边长, 则递推式为:
        dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) if matrix[i][j]=='1'
        """
        if not matrix:
            return 0

        r,c=len(matrix),len(matrix[0])

        dp=[[0]*c for i in range(r)]

        for i in range(r):
            dp[i][0]=int(matrix[i][0])
        for i in range(c):
            dp[0][i]=int(matrix[0][i])


        for i in range(1,r):
            for j in range(1,c):
                if matrix[i][j]=='1':
                    dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1

        length=0
        for i in range(r):
            length=max(length,max(dp[i]))

        return length**2
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(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        dp的维度分别是len(matrix)+1,len(matrix[0])+1，因此
        dp[i][j]表示matrix中以第i-1行第j-1列为右下角所能构成的最大正方形边长, 则递推式为:
        dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) if matrix[i-1][j-1]=='1'
        """
        if not matrix:
            return 0

        r,c=len(matrix),len(matrix[0])

        dp=[[0]*(c+1) for i in range(r+1)]

        length=0
        for i in range(1,r+1):
            for j in range(1,c+1):
                if matrix[i-1][j-1]=='1':
                    dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
                    length=max(length,dp[i][j])


        return length**2