1277. 统计全为 1 的正方形子矩阵

🟠   🔖  数组 动态规划 矩阵  🔗 力扣 LeetCode

题目

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix =

[

[0,1,1,1],

[1,1,1,1],

[0,1,1,1]

]

Output: 15

Explanation:

There are 10 squares of side 1.

There are 4 squares of side 2.

There is 1 square of side 3.

Total number of squares = 10 + 4 + 1 = 15.

Example 2:

Input: matrix =

[

[1,0,1],

[1,1,0],

[1,1,0]

]

Output: 7

Explanation:

There are 6 squares of side 1.

There is 1 square of side 2.

Total number of squares = 6 + 1 = 7.

Constraints:

• 1 <= arr.length <= 300
• 1 <= arr[0].length <= 300
• 0 <= arr[i][j] <= 1

题目大意

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

示例 1：

输入： matrix =

[

[0,1,1,1],

[1,1,1,1],

[0,1,1,1]

]

输出： 15

解释：

边长为 1 的正方形有 10 个。

边长为 2 的正方形有 4 个。

边长为 3 的正方形有 1 个。

正方形的总数 = 10 + 4 + 1 = 15.

示例 2：

输入： matrix =

[

[1,0,1],

[1,1,0],

[1,1,0]

]

输出： 7

解释：

边长为 1 的正方形有 6 个。

边长为 2 的正方形有 1 个。

正方形的总数 = 6 + 1 = 7.

提示：

• 1 <= arr.length <= 300
• 1 <= arr[0].length <= 300
• 0 <= arr[i][j] <= 1

解题思路

可以使用动态规划的方法来解决这道题。

1. 动态规划数组：

   • 创建一个与输入矩阵大小相同的动态规划数组 dp，dp[i][j] 表示以 (i, j) 为右下角的正方形子矩阵的最大边长。
   • 如果 matrix[i][j] 是 1，则 dp[i][j] 的值取决于它的上、左和左上对角的值：

   dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

   • 否则，如果 matrix[i][j] 是 0，则 dp[i][j] 的值为 0。

2. 总计数：

   • 每次更新 dp[i][j] 时，将其值累加到总计数中，这样就可以在遍历完成后得到所有正方形子矩阵的总数。

3. 边界条件：

   • 对于第一行和第一列的元素，dp[i][j] 只能等于 matrix[i][j] 本身，因为它们不能形成更大的正方形。

复杂度分析

• 时间复杂度：O(m * n)，其中 m 是矩阵的行数，n 是矩阵的列数，需要遍历整个矩阵一次。
• 空间复杂度：O(m * n)，使用一个与输入矩阵相同大小的动态规划数组。

代码

/**
 * @param {number[][]} matrix
 * @return {number}
 */
var countSquares = function (matrix) {
	if (!matrix || matrix.length == 0 || matrix[0].length == 0) return 0;
	const m = matrix.length,
		n = matrix[0].length;
	let dp = new Array(m).fill(0).map((i) => new Array(n).fill(0));
	let res = 0;
	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			if (matrix[i][j] == 1) {
				// 第一行或第一列
				if (i == 0 || j == 0) {
					dp[i][j] = 1;
				} else {
					dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1;
				}

				// 更新总计数
				res += dp[i][j];
			}
		}
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度
2087	网格图中机器人回家的最小代价		贪心 数组
2088	统计农场中肥沃金字塔的数目		数组 动态规划 矩阵