问题

统计所有元素和 ≤ k 的左上角为 (0,0) 的子矩阵个数。

方法一：二维前缀和

思路

  • 用 sum[i+1][j+1] 表示 grid 中 (0,0) 到 (i,j) 的元素和
  • 转移公式：sum[i+1][j+1] = sum[i][j+1] + sum[i+1][j] - sum[i][j] + grid[i][j]
    • 加上方块 + 加左方块 - 减重叠部分 + 加当前元素
// 二维前缀和
class Solution {
public:
    int countSubmatrices(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        int ans = 0;
        vector<vector<int>> sum(m+1, vector<int>(n+1));

        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                sum[i+1][j+1] = sum[i][j+1] + sum[i+1][j] - sum[i][j] + grid[i][j];
                if(sum[i+1][j+1] <= k) ++ans;
                else break;  // 优化：该行后续必然超过 k
            }
        }
        return ans;
    }
};

复杂度：时间 O(mn)，空间 O(mn)

方法一拓展：原地二维前缀和

直接在 grid 数组上修改，省去额外空间。

// 原地二维前缀和
class Solution {
public:
    int countSubmatrices(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        int ans = 0;

        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(i > 0) grid[i][j] += grid[i-1][j];
                if(j > 0) grid[i][j] += grid[i][j-1];
                if(i > 0 && j > 0) grid[i][j] -= grid[i-1][j-1];

                if(grid[i][j] <= k) ++ans;
                else break;  // 优化：该行后续必然超过 k
            }
        }
        return ans;
    }
};

复杂度：时间 O(m*n)，空间 O(1)

方法二：维护每列的元素和

思路

  • 逐行扫描，用 col_sum[j] 维护每列的累积和
  • 每行从左到右扫，累加行前缀和 s
  • 一旦 s > k 就停止（后续必然更大）
// 维护每列元素和
class Solution {
public:
    int countSubmatrices(vector<vector<int>>& grid, int k) {
        int n = grid[0].size();
        vector<int> col_sum(n);
        int ans = 0;

        for(auto &row : grid) {
            int s = 0;
            for(int j = 0; j < n; ++j) {
                col_sum[j] += row[j];
                s += col_sum[j];
                if(s > k) break;
                ++ans;
            }
        }
        return ans;
    }
};

复杂度：时间 O(m*n)，空间 O(n)

总结

方法 空间 优点
二维前缀和 O(m*n) 逻辑清晰，易理解
原地二维前缀和 O(1) 空间高效
维护每列和 O(n) 最优空间 + 最清晰逻辑

推荐：方法二（维护每列和）= 最优空间 + 最清晰逻辑```