题目:
给定一个矩阵,该矩阵只包含0和1,输出该矩阵中最大正方形区域的面积 如: 00011110 00001111 11101111 最大是 3X3 的正方形,输出为 9
解题:
1.参考相关博客(链接见下文) 先新建一个全为0,行数和列相等的列表 dp,设置一个最大值 maxSquare 1)第一行和第一列,如果等于1,则dp对应的值为1 2)除此之外,如果该值等于1,取该值左边、上边、左上中的最小值+1 该值为dp对应的值 3)取 maxSquare 和该值的最大值,赋值给 maxSquare 4)返回 maxSquare * maxSquare 以上是取1中的最大正方形,取0中的最大正方形也类似,最后取 1和0中最大值中的最大值即可
代码:
1 from typing import List 2 """ 3 输出矩阵最大面积 4 """ 5 class Solution: 6 def maximalSquare(self, matrix: List[List[str]]) -> int: 7 #长度为0,直接返回0 8 if len(matrix) == 0 or len(matrix[0]) == 0: 9 return 0 10 11 maxSide1 = 0 12 maxSide0 = 0 13 rows, columns = len(matrix), len(matrix[0]) 14 15 #新增二个全为0的数组 16 dp1 = [[0] * columns for _ in range(rows)] 17 dp0 = [[0] * columns for _ in range(rows)] 18 19 for i in range(rows): 20 for j in range(columns): 21 #取1中的最大正方形 22 if matrix[i][j] == '1': 23 # 第一行和第一列为1时,新数组值为1 24 if i == 0 or j == 0: 25 dp1[i][j] = 1 26 #取改值左边、上边、左上中的最小值+1 27 else: 28 dp1[i][j] = min(dp1[i - 1][j], dp1[i][j - 1], dp1[i - 1][j - 1]) + 1 29 maxSide1 = max(maxSide1, dp1[i][j]) 30 31 # 取0中的最大正方形 32 if matrix[i][j] == '0': 33 # 第一行和第一列为0时,新数组值为1 34 if i == 0 or j == 0: 35 dp0[i][j] = 1 36 # 取改值左边、上边、左上中的最小值+1 37 else: 38 dp0[i][j] = min(dp0[i - 1][j], dp0[i][j - 1], dp0[i - 1][j - 1]) + 1 39 maxSide0 = max(maxSide0, dp0[i][j]) 40 41 #取0,1中的最大值 42 maxSide = max(maxSide1,maxSide0) 43 maxSquare = maxSide * maxSide 44 return maxSquare 45 46 s = Solution() 47 print(s.maximalSquare(['1110','1110','1110']))
参考博客:https://blog.csdn.net/AI414010/article/details/108985709
题目来源:
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximal-square/