[leetcode] 221.Maximal Square - 程序园
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.
题意：
给定一个二维数组，包含0和1，返回最大的全是1的正方形的面积。
思路：
采用动态规划的思路完成。记录以数组中某个点作为正方形的右下角对应的正方形的边长。
- 如果该点元素是0，那么以该点作为正方形的右下角对应的正方形的边长就为0。
- 如果该点元素是1，那么边长由什么决定呢？比如求edge[i][j]时，我们需要依赖的有edge[i-1][j],edge[i][j-1],edge[i-1][j-1]。这三个点是与[i][j]位置相近的三个点，只有这三个点都不是0，才可以构成边长超过1的正方形。因为边长为2以上的正方形最少包括除[i][j]之外的[i-1][j], [i][j-1]，[i-1][j-1]这三个点。那么我们考虑以这三个点作为右下角的正方形的边长。我们知道以[i][j]这个点作为正方形，最多可以往左边延伸的长度是edge[i][j-1]，edge[i-1][j-1]的较小者，同理往上最多延伸edge[i-1][j],edge[i-1][j-1]。那么也就是说应该取三者中的最小者，作为延伸的长度。以下图片，红色正方形代表的是以[i-1][j-1]为右下角的，两个蓝色的代表的是以[i-][j-1],[i-1][j]为右下角的，橙色的是当前的。
Read full article from [leetcode] 221.Maximal Square - 程序园
No comments:
Post a Comment