最大正方形
# 📃 题目描述
题目链接:221. 最大正方形 (opens new window)
# 🔔 解题思路
class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int row = matrix.length;
int col = matrix[0].length;
// dp[i][j] 表示以 matrix[i][j] 为右下角的最大正方形的边长
int[][] dp = new int[row][col];
int maxEdge = 0;
for (int i = 0; i < row; i ++) {
for (int j = 0; j < col; j ++) {
if (matrix[i][j] == '1') {
if (i == 0 || j == 0) {
dp[i][j] = 1;
}
else {
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}
}
maxEdge = Math.max(maxEdge, dp[i][j]);
}
}
return maxEdge * maxEdge;
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10