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

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

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

思路分析

解法一：动态规划（推荐）

核心思路：

dp[i][j] 表示以 (i,j) 为右下角的最大全 1 正方形边长。

若 matrix[i][j] == 1，则 dp[i][j] = 1 + min(上, 左, 左上)。

累加所有 dp[i][j] 即为正方形子矩阵数量。

复杂度分析：

时间复杂度：O(m * n)，其中 m、n 表示矩阵尺寸。

空间复杂度：O(n)，使用一维滚动数组。

class Solution {
    public int countSquares(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[] dp = new int[n + 1];
        int res = 0;

        for (int i = 1; i <= m; i++) {
            int prev = 0;
            for (int j = 1; j <= n; j++) {
                int temp = dp[j];
                if (matrix[i - 1][j - 1] == 1) {
                    dp[j] = Math.min(Math.min(dp[j], dp[j - 1]), prev) + 1;
                    res += dp[j];
                } else {
                    dp[j] = 0;
                }
                prev = temp;
            }
        }

        return res;
    }
}

func countSquares(matrix [][]int) int {
	m, n := len(matrix), len(matrix[0])
	dp := make([]int, n+1)
	res := 0

	for i := 1; i <= m; i++ {
		prev := 0
		for j := 1; j <= n; j++ {
			temp := dp[j]
			if matrix[i-1][j-1] == 1 {
				minVal := dp[j]
				if dp[j-1] < minVal {
					minVal = dp[j-1]
				}
				if prev < minVal {
					minVal = prev
				}
				dp[j] = minVal + 1
				res += dp[j]
			} else {
				dp[j] = 0
			}
			prev = temp
		}
	}

	return res
}

相似题目

题目	难度	考察点
221. 最大正方形	中等	动态规划
304. 二维区域和检索 - 矩阵不可变	中等	前缀和
64. 最小路径和	中等	动态规划
85. 最大矩形	困难	栈
1292. 元素和小于等于阈值的正方形的最大边长	中等	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/86850077