统计全为 1 的正方形子矩阵
# 📃 题目描述
题目链接:1277. 统计全为 1 的正方形子矩阵 (opens new window)
# 🔔 解题思路
和 221. 最大正方形 (opens new window) 思路一样,关键就在于:dp[i][j] = x
也表示以 (i, j)
为右下角的正方形的数目为 x
(即边长为 1, 2, ..., x
的正方形各一个)
class Solution {
public int countSquares(int[][] 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];
// 全 1 正方形数目
int res = 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;
}
}
res += dp[i][j];
}
}
return res;
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

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