📘 題目敘述
給你一個 0-indexed 的整數矩陣 grid 和一個整數 k。
請回傳包含 grid 左上角元素的子矩陣中，總和小於等於 k 的子矩陣數量。
條件限制
m == grid.lengthn == grid[i].length1 <= n, m <= 10000 <= grid[i][j] <= 10001 <= k <= 10^9
🧠 解題思路
這題最重要的觀察是：
題目要求子矩陣一定要包含左上角元素。
所以所有合法子矩陣，其實左上角都固定是 (0,0)。
也就是說，我們要數的子矩陣都可以寫成：
- 左上角固定
(0,0) - 右下角是某個
(i,j)
這樣一來，題目就變成：
- 對每個
(i,j) - 算出前綴矩陣
(0,0) ~ (i,j)的總和 - 如果這個總和
<= k，那這個子矩陣就算一個答案
所以我這份程式就是直接做二維 prefix sum。
我用 sum[i][j] 表示：
- 從左上角
(0,0)到(i,j)這整塊矩形的總和
這樣每算出一格 sum[i][j]，就可以直接判斷：
sum[i][j] <= k嗎？
如果是，就代表這個以前綴形式表示的子矩陣符合條件，答案加一。
也就是說，這題的核心就是：
因為所有合法子矩陣都一定從
(0,0)開始，所以只要算每個位置的二維前綴和，再檢查是否<= k即可。
所有變數
m：列數n：行數sum：二維 prefix sum，sum[i][j]表示從(0,0)到(i,j)的總和count：符合條件的子矩陣數量now：目前位置(i,j)的前綴矩陣總和
🪜 主要流程步驟
1. 先建立 prefix sum 矩陣，並初始化左上角
這裡先記下矩陣大小，然後建立一個同大小的 sum。
其中：
sum[0][0]就是只包含左上角一格的前綴矩陣總和- 所以它直接等於
grid[0][0]
2. 先判斷左上角這一格本身是不是答案
int count = 0;
if (sum[0][0] <= k) {
count++;
} else {
return 0;
}
因為所有合法子矩陣都一定包含 (0,0)，
所以最小的候選子矩陣就是只包含 (0,0) 這一格。
如果這一格的值都已經大於 k，那後面任何更大的前綴矩陣只會更大，不可能再小於等於 k。
所以這裡如果 sum[0][0] > k，就可以直接回傳 0。
3. 先處理第一欄，因為它只能從上面累加
for (int s = 1; s < m; s++) {
sum[s][0] = grid[s][0] + sum[s - 1][0];
if (sum[s][0] <= k) {
count++;
}
}
第一欄的前綴矩陣只有一種延伸方式：
- 從上面一直往下加
所以：
sum[s][0] = grid[s][0] + sum[s - 1][0]
這代表 (0,0) ~ (s,0) 這條直條矩形的總和。
每算完一格，就檢查一次是否 <= k，如果是就把它算進答案。
4. 再處理第一列，因為它只能從左邊累加
第一列和第一欄是對稱的。
這裡的 sum[0][l] 表示：
(0,0) ~ (0,l)這條橫向矩形的總和
因為第一列沒有上面可以參考，所以只要一路往左邊累加即可。
5. 一般位置用二維 prefix sum 公式計算
這一段是整題最核心的部分。
對一般位置 (i,j)，sum[i][j] 要表示從 (0,0) 到 (i,j) 的總和。
所以使用標準二維 prefix sum 公式：
- 上面那塊：
sum[i - 1][j] - 左邊那塊：
sum[i][j - 1] - 左上角那塊被重複算了一次，所以要扣掉：
sum[i - 1][j - 1] - 最後再加上目前這格
grid[i][j]
也就是：
sum[i][j] = grid[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
你的程式裡是先用 now 暫存，再存回 sum[i][j]。
每算完這個前綴矩陣的總和後，就立刻檢查：
now <= k
如果成立，表示這個以 (0,0) 為左上角、(i,j) 為右下角的子矩陣符合條件，答案加一。
6. 為什麼這樣就數到了所有合法子矩陣
因為題目要求：
- 子矩陣一定要包含左上角元素
所以任何合法子矩陣都不可能從別的地方開始，它的左上角一定是 (0,0)。
因此所有合法子矩陣都能唯一對應到一個右下角 (i,j)。
也就是說：
- 枚舉所有
(i,j) - 計算
(0,0) ~ (i,j)的總和 - 判斷是否
<= k
這樣就完整數到了所有答案，而且不會重複。
7. 最後回傳 count
return count;
當所有位置都處理完後，count 就是符合條件的子矩陣總數。
⏱️ 複雜度
設 m = grid.length，n = grid[0].length。
- 時間複雜度：
O(mn)每個位置都只會被處理一次。
- 空間複雜度：
O(mn)額外使用了一個
m x n的sum矩陣來記錄前綴和。
💻 程式碼實作
class Solution {
public:
int countSubmatrices(vector<vector<int>>& grid, int k) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> sum(m, vector<int>(n));
sum[0][0] = grid[0][0];
int count = 0;
if (sum[0][0] <= k) {
count++;
} else {
return 0;
}
for (int s = 1; s < m; s++) {
sum[s][0] = grid[s][0] + sum[s - 1][0];
if (sum[s][0] <= k) {
count++;
}
}
for (int l = 1; l < n; l++) {
sum[0][l] = grid[0][l] + sum[0][l - 1];
if (sum[0][l] <= k) {
count++;
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
int now = grid[i][j];
now = now + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
sum[i][j] = now;
if (now <= k) {
count++;
}
}
}
return count;
}
};
🔗 題目連結
https://leetcode.com/problems/count-submatrices-with-top-left-element-and-sum-less-than-k/