边界都是1的最大正方形大小

题目

　　给定一个N×N的矩阵matrix，在这个矩阵中，只有0和1两种值，返回边框全是1的最大正方形的边长长度。 
　　例如： 
　　０　１　１　１　１ 
　　０　１　０　０　１ 
　　０　１　０　０　１ 
　　０　１　０　１　１ 
　　其中，边框全是1的最大正方形的大小是4*4，返回4。

基本思路

　比较容易理解的方法：

矩阵中一共有N*N个位置。Ｏ(N2N2)

每一个位置都可以成为边长为N~1的正方形的左上角。O(N)

如何检查一个位置是否可以成为边长为Ｎ的正方形的左上角呢？遍历这个边长为Ｎ的正方形边界看是否只由１构成，也就是走过４个边的长度(4N)。O(N)

所以总的时间复杂度O(N4N4).

　　该方法可以进行优化，将步骤三的时间复杂度降为O(1)，总的时间复杂度降为O(N3N3)。思路就是通过预处理，得到两个辅助矩阵right、down。right[i][j]的含义是，从位置（i，j）开始，向右一共有多少个连续的1；down[i][j]的含义是，从位置（i，j）开始，向下一共有多少个连续的1。利用动态规划很容易得到这两个辅助矩阵。

　　接下来，如何检查一个位置是否可以成为边长为N的正方形的左上角呢？只要判断边框左上角的位置向右以及向下连续的1的个数是否大于N，以及边框左下角的位置向右连续的1的个数是否大于N、以及边框右上角的位置向下连续的1的个数是否大于N。
 

def getMaxSize(matrix):if matrix == None or len(matrix) == 0:return 0right = [[0 for i in range(len(matrix[0]))] for j in range(len(matrix))]down = [[0 for i in range(len(matrix[0]))] for j in range(len(matrix))]setBorderMap(matrix,right,down)size_result = []for size in range(min(len(matrix),len(matrix[0])),0,-1):if hasSizeOfBorder(size,right,down):size_result.append(size)if len(size_result)==0:return 0else:return max(size_result)def setBorderMap(matrix,right,down):row = len(matrix) - 1col = len(matrix[0]) - 1if matrix[row][col] == 1:right[row][col] = 1down[row][col] = 1for i in range(len(matrix)-2,-1,-1):if matrix[i][col] == 1:right[i][col] = 1down[i][col] = down[i+1][col] + 1for j in range(len(matrix[0])-2,-1,-1):if matrix[row][j] == 1:right[row][j] = right[row][j+1] + 1down[row][j] = 1for i in range(len(matrix)-2,-1,-1):for j in range(len(matrix[0])-2,-1,-1):if matrix[i][j] == 1:right[i][j] = right[i][j+1] + 1down[i][j] = down[i+1][j] + 1def hasSizeOfBorder(size,right,down):for i in range(len(right)-size+1):for j in range(len(right[0])-size+1):if right[i][j] >= size and down[i][j] >= size and right[i+size-1][j] >= size and down[i][j+size-1]>=size:return Truereturn Falsematrix = [[0,1,1,1,1],[0,1,0,0,1],[0,1,0,0,1],[0,1,1,1,1],[0,1,0,1,1]] getMaxSize(matrix)

 

总结

以上是生活随笔为你收集整理的边界都是1的最大正方形大小的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。