LeetCode : 221. Maximal Square 最大正方形 た 入场券 2021-06-24 16:11 348阅读 0赞 **试题** 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 0 Output: 4 **代码** 很好理解的动归。dp为以当前位置为最大正方形右下角角点的边长。dp\[i\]\[j\]主要有dp\[i\]-1\[j-1\];dp\[i-1\]\[j\]; dp\[i\]\[j-1\] 三个长度限制。初始化方式注意一下。 class Solution { public int maximalSquare(char[][] matrix) { if(matrix==null || matrix.length==0 || matrix[0].length==0) return 0; int row = matrix.length, col = matrix[0].length; int[][] dp = new int[row+1][col+1]; int max = 0; for(int i=1; i<=row; i++){ for(int j=1; j<=col; j++){ if(matrix[i-1][j-1]=='1'){ dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1; max = Math.max(dp[i][j], max); } } } return max*max; } } 节省空间:
还没有评论,来说两句吧...