221. Maximal Square - Medium
发布时间:2020-12-14 04:29:16 所属栏目:大数据 来源:网络整理
导读: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 01 0 1 1 11 1 1 1 11 0 0 1 0Output: 4 ? 用dp。二重循环,如果dp[i][j]=1,检查一下它的上、左、右,取
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]=1,检查一下它的上、左、右,取三个值中的最小值+1 (dp[i][j]),再更新一下max。 注意dp的长度比matrix多1. 时间:O(N^2),空间O(N^2) class Solution { public int maximalSquare(char[][] matrix) { if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0; int m = matrix.length,n = matrix[0].length,max = 0; int[][] dp = new int[m+1][n+1]; for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { if(matrix[i-1][j-1] == ‘1‘) { dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i][j-1],dp[i-1][j])) + 1; max = Math.max(max,dp[i][j]); } } } return max * max; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
推荐文章
站长推荐
热点阅读