Problem: 1277. 統計全為 1 的正方形子矩陣

整體思路

這段代碼旨在解決一個經典的二維矩陣問題：統計全為 1 的正方形子矩陣個數 (Count Square Submatrices with All Ones)。問題要求計算在一個由 0 和 1 組成的矩陣中，所有元素都為 1 的正方形子矩陣的總數量。

該算法采用了一種非常高效的 動態規劃 (Dynamic Programming) 方法。其核心思想是構建一個 DP 表，并利用子問題的解來推導當前問題的解。

1. 狀態定義 (DP State)：

   • 算法創建了一個 dp 數組，其大小比原矩陣 matrix 大一圈（[m+1][n+1]），這種“填充”技巧可以簡化邊界條件的處理。
   • dp[i][j] 的核心含義是：以 matrix[i-1][j-1] 為右下角 的、全由 1 組成的最大正方形的 邊長。

2. 狀態轉移方程：

   • 算法遍歷原矩陣 matrix 的每一個單元格 (i, j)。
   • 只有當 matrix[i][j] 本身為 1 時，它才有可能成為某個正方形的右下角。
   • 如果 matrix[i][j] == 1，那么以它為右下角的最大正方形的邊長，取決于其 上方、左方 和 左上方 三個相鄰位置所能形成的最大正方形。
   • 具體來說，一個新的、更大的 k x k 正方形，必須依賴于它旁邊已經存在三個 (k-1) x (k-1) 的正方形。因此，新的邊長受限于這三者中的最小值。
   • 狀態轉移方程為：
     dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j], dp[i][j]) + 1
     （這里的 dp 索引都比 matrix 的索引大 1）。

3. 核心計數邏輯：

   • 這是該算法最巧妙的一點。dp[i+1][j+1] 的值，比如說 k，不僅代表以 matrix[i][j] 為右下角的最大正方形邊長是 k，它還隱含了以該點為右下角的、邊長為 k-1, k-2, …, 1 的正方形也必然存在。
   • 因此，dp[i+1][j+1] 的值 k，恰好等于以 matrix[i][j] 為右下角的所有正方形的總數。
   • 所以，在計算出每個 dp[i+1][j+1] 的值之后，直接將其累加到最終結果 ans 中，就可以統計出矩陣中所有的正方形。

4. 算法流程：

   • 創建一個 dp 表。
   • 遍歷輸入矩陣 matrix。
   • 如果 matrix[i][j] 是 1，則根據狀態轉移方程計算 dp[i+1][j+1] 的值。
   • 將計算出的 dp[i+1][j+1] 累加到 ans。
   • 如果 matrix[i][j] 是 0，則 dp[i+1][j+1] 保持默認值 0，對 ans 沒有貢獻，這符合邏輯。
   • 遍歷結束后返回 ans。

完整代碼

class Solution {/*** 統計一個二維矩陣中，所有元素都為 1 的正方形子矩陣的總數量。* @param matrix 一個由 0 和 1 組成的二維整數數組* @return 全為 1 的正方形子矩陣的總數*/public int countSquares(int[][] matrix) {int m = matrix.length;int n = matrix[0].length;// dp 表：dp[i][j] 表示以 matrix[i-1][j-1] 為右下角的最大正方形的邊長。// 使用 m+1 和 n+1 的大小是為了增加一圈“哨兵”0，簡化邊界條件的處理。int[][] dp = new int[m + 1][n + 1];// ans: 用于累計正方形的總數。int ans = 0;// 遍歷原始矩陣的每一個單元格for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {// 只有當當前單元格為 1 時，它才可能成為正方形的一部分if (matrix[i][j] == 1) {// 狀態轉移方程：// 以 (i, j) 為右下角的最大正方形的邊長，取決于其左、上、左上三個方向// 形成的最大正方形邊長中的最小值，然后再加上當前這個單元格（+1）。// dp[i+1][j+1] 對應 matrix[i][j]。dp[i + 1][j + 1] = Math.min(Math.min(dp[i][j + 1], dp[i + 1][j]), dp[i][j]) + 1;// 核心計數邏輯：// dp[i+1][j+1] 的值 k，代表以 (i, j) 為右下角的正方形有 k 個// (邊長分別為 1, 2, ..., k)。// 因此，直接將這個值累加到總數中。ans += dp[i + 1][j + 1];}}}// 返回最終統計的結果return ans;}
}

時空復雜度

時間復雜度：O(m * n)

1. 循環：算法的核心是兩個嵌套的 for 循環，它們完整地遍歷了輸入矩陣 matrix 的每一個單元格。
   • 外層循環執行 m 次（m 是矩陣的行數）。
   • 內層循環執行 n 次（n 是矩陣的列數）。
2. 循環內部操作：
   • 在循環的每一次迭代中，執行的操作（if 判斷、Math.min、數組讀寫、加法）都是常數時間復雜度的，即 O(1)。

綜合分析：
算法的總時間復雜度是 m * n 次 O(1) 操作，因此最終的時間復雜度為 O(m * n)。

空間復雜度：O(m * n)

1. 主要存儲開銷：算法創建了一個名為 dp 的二維數組來存儲動態規劃的狀態。
2. 空間大小：dp 數組的維度是 (m + 1) x (n + 1)。其占用的空間與輸入矩陣的大小 m * n 成正比。
3. 其他變量：m, n, ans, i, j 等變量都只占用常數級別的空間。

綜合分析：
算法所需的額外輔助空間主要由 dp 數組決定。因此，其空間復雜度為 O(m * n)。

參考靈神