最大正方形

发表于

这是我参与11月更文挑战的第26天，活动详情查看：2021最后一次更文挑战

问题描述

221. 最大正方形

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

示例：

输入：matrix = [[“1”,”0”,”1”,”0”,”0”], [“1”,”0”,”1”,”1”,”1”], [“1”,”1”,”1”,”1”,”1”], [“1”,”0”,”0”,”1”,”0”]]

输出：4

image-20211122134648361

分析问题

我们都知道正方形的面积等于边长的平方，要想求出最大的正方形面积，首先需要找到最大正方形的边长，然后在计算平方就好。

最直观的解法就是使用暴力法来求解。具体来说，我们遍历矩阵中的每一个元素，每次遇到1时，则将该元素作为正方形的左上角；然后根据左上角所在的行和列计算可能的最大正方形的边长（每次在下方新增一行以及在右方新增一列，判断新增的行和列是否满足所有元素都是 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
32
33
34
35
36
ini复制代码class Solution:
    def maximalSquare(self, matrix):
        #如果矩阵为空，直接返回0
        if len(matrix) == 0 \
                or len(matrix[0]) == 0:
            return 0
        #最大的边长
        max_length=0
        rows, columns = len(matrix), len(matrix[0])

        for i in range(rows):
            for j in range(columns):
                #遇到一个 1 作为正方形的左上角
                if matrix[i][j] == '1':
                    max_length = max(max_length, 1)
                    #求出超出边界的最小值
                    current_edge = min(rows - i, columns - j)
                    for k in range(1, current_edge):
                        #判断新增的一行一列是否均为1
                        tag = True
                        #判断对角线是否为1，如果为0，直接退出，
                        if matrix[i + k][j + k] == '0':
                            break
                        for m in range(k):
                            #判断对应的列或者行是否全为1
                            if matrix[i + k][j + m] == '0' or matrix[i + m][j + k] == '0':
                                tag = False
                                break
                        if tag:
                            #如果新增的一行一列均为1，则增加边长
                            max_length = max(max_length, k + 1)
                        else:
                            break
        #返回最大面积
        result = max_length * max_length
        return result

该算法的时间复杂度是 O(m * n * min(m, n) ^ 2)，其中 m 和 n 是矩阵的行数和列数；空间复杂度是O(1)。显然该算法的时间复杂度太高，下面我们来看一下如何进行优化求解。

这道题我们可以使用动态规划来求解。我们用 dp[i] [j] 表示以 (i，j) 为右下角，且只包含 1 的正方形的边长的最大值。在求出所有的dp[i] [j]的值以后，那么其中的最大值就是矩阵中只包含1的正方形的边长的最大值，其平方就是最大正方形的面积。下面我们来看一下如何来求解dp[i] [j] 。

对于矩阵中的每一个位置（i，j），检查其对应的值。

  • 如果该位置是0，那么dp[i] [j] =0，因为当前位置不可能在由1组成的正方形中；
  • 如果该位置是1，那么dp[i] [j] 的值由其上边，左边以及左上角三个相邻位置的值决定。即当前位置的值等于三个相邻位置元素对应的值的最小值加1。

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

image-20211122172537892

我们来看一下边界条件。当i=0或者j=0时，如果矩阵中位置为(i, j) 的值为1，那么以位置（i,j）为右下角的矩阵的边长只能是1，即此时dp[i] [j] = 1。

当matrix 为 [[“1”,”0”,”1”,”0”,”0”], [“1”,”0”,”1”,”1”,”1”], [“1”,”1”,”1”,”1”,”1”], [“1”,”0”,”0”,”1”,”0”]] 时，其状态转移矩阵如下图所示。

image-20211122174241556

下面我们来看一下代码的实现。

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
ini复制代码class Solution:
    def maximalSquare(self, matrix):
        #如果矩阵为空，直接返回0
        if len(matrix) == 0 \
                or len(matrix[0]) == 0:
            return 0

        max_edge = 0
        m, n = len(matrix), len(matrix[0])
        #初始化一个状态转移矩阵
        dp = [[0] * n for _ in range(m)]

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == '1':
                    #边界条件
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                    max_edge = max(max_edge, dp[i][j])

        #求出最大正方形
        result = max_edge * max_edge
        return result

该算法的时间复杂度是O(m*n)，其中m、n分别为矩阵的行和列。空间复杂度也是O(m * n)。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%