本文主要是介绍[LeetCode] 221. Maximal Square，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目内容
https://leetcode-cn.com/problems/maximal-square/
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
Example:Input: 1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0Output: 4题目思路
这道题目可以采用动态规划的方法。对于矩阵中的某个元素来说，动态规划的结果就是以此元素为正方形右下角的正方形的最大边长。那么如果是0，则必定不是正方形；如果是1，那么就考察左侧，右侧和上侧的部分看看是否也能构成正方形。并且根据木桶效应，选择最小的数值。
程序代码
class Solution(object):def maximalSquare(self, matrix):""":type matrix: List[List[str]]:rtype: int"""if not matrix:return 0wid,lgt=len(matrix),len(matrix[0])res=0for i in range(wid):matrix[i][0]=int(matrix[i][0])res=max(matrix[i][0],res)for j in range(lgt):matrix[0][j]=int(matrix[0][j])res=max(matrix[0][j],res)for i in range(1,wid):for j in range(1,lgt):matrix[i][j]=int(matrix[i][j])if matrix[i][j]==1:matrix[i][j]+=min(matrix[i-1][j-1],matrix[i-1][j],matrix[i][j-1])res=max(matrix[i][j],res)return res**2
这篇关于[LeetCode] 221. Maximal Square的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
