Leetcode: Maximal Square
LeetCode Square
2023-09-11 14:14:07 时间
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.
dp问题,用一个dp[i][j]保存matrix[i][j]作为右下节点的时候的最大矩形的边长
if (matrix[i][j] == '0') dp[i][j] = 0;
else dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1;
1 public class Solution { 2 public int maximalSquare(char[][] matrix) { 3 int res = 0; 4 if (matrix==null || matrix.length==0 || matrix[0].length==0) return res; 5 int[][] dp = new int[matrix.length][matrix[0].length]; 6 int maxEdge = 0; 7 for (int i=0; i<matrix.length; i++) { 8 if (matrix[i][0] == '1') dp[i][0] = 1; 9 else dp[i][0] = 0; 10 maxEdge = Math.max(maxEdge, dp[i][0]); 11 } 12 for (int j=1; j<matrix[0].length; j++) { 13 if (matrix[0][j] == '1') dp[0][j] = 1; 14 else dp[0][j] = 0; 15 maxEdge = Math.max(maxEdge, dp[0][j]); 16 } 17 for (int i=1; i<matrix.length; i++) { 18 for (int j=1; j<matrix[0].length; j++) { 19 if (matrix[i][j] == '0') { 20 dp[i][j] = 0; 21 continue; 22 } 23 dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1; 24 maxEdge = Math.max(maxEdge, dp[i][j]); 25 } 26 } 27 return maxEdge * maxEdge; 28 } 29 }
相关文章
- Leetcode: Matchsticks to Square && Grammar: reverse an primative array
- Leetcode: Combination Sum II
- Leetcode: Merge k Sorted List
- LeetCode: Ugly Number II
- Candy [leetcode] O(n)时间复杂度,O(1)空间复杂度的方法
- [LeetCode] 1263. Minimum Moves to Move a Box to Their Target Location 推箱子
- [LeetCode] 1200. Minimum Absolute Difference 最小绝对差
- [LeetCode] 1177. Can Make Palindrome from Substring 构建回文串检测
- [LeetCode] 1169. Invalid Transactions 查询无效交易
- [LeetCode] 953. Verifying an Alien Dictionary 验证外星文字典
- [LeetCode] 879. Profitable Schemes 盈利方案
- [LeetCode] N-ary Tree Preorder Traversal N叉树的前序遍历
- [LeetCode] 711. Number of Distinct Islands II 不同岛屿的个数之二
- [LeetCode] Remove Comments 移除注释
- [LeetCode] 4 Keys Keyboard 四键的键盘
- [LeetCode] 598. Range Addition II 范围相加之二
- [LeetCode] Longest Absolute File Path 最长的绝对文件路径
- leetcode 221. Maximal Square 最大正方形(中等)
- leetcode算法203.移除链表元素