3070.元素和小于等于 k 的子矩阵的数目：原地修改(前缀和思想)

【LetMeFly】3070.元素和小于等于 k 的子矩阵的数目：原地修改(前缀和思想)

力扣题目链接：https://leetcode.cn/problems/count-submatrices-with-top-left-element-and-sum-less-than-k/

给你一个下标从 0 开始的整数矩阵 grid 和一个整数 k。

返回包含 grid 左上角元素、元素和小于或等于 k 的 子矩阵的数目。

 

示例 1：

输入：grid = [[7,6,3],[6,6,1]], k = 18
输出：4
解释：如上图所示，只有 4 个子矩阵满足：包含 grid 的左上角元素，并且元素和小于或等于 18 。

示例 2：

输入：grid = [[7,2,9],[1,5,0],[2,6,6]], k = 20
输出：6
解释：如上图所示，只有 6 个子矩阵满足：包含 grid 的左上角元素，并且元素和小于或等于 20 。

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= n, m <= 1000
• 0 <= grid[i][j] <= 1000
• 1 <= k <= 109

解题方法：前缀和原地修改

第一层循环从上到下第二层循环从左到右遍历一遍$grid$数组，在遍历过程中把$grid[i][j]$的值修改为从左上角到这个元素的子矩阵元素之和。

怎么$O(1)$时间得到右下角为$(i,j)$的子矩阵之和？借助前面的遍历结果即可：

• 如果$i$和$j$都大于$0$，则$grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1]$：

  1 2
  3 4

  如图矩阵在计算左上角到右下角的$4$的时候，可以借助左上角到$4$上面$2$的元素和 + 左上角到$4$左边$3$的元素和 - 计算重复的左上角到$4$左上角$1$的元素和。

• 如果$i$大于$0$而$j$等于$0$，则直接加上这个元素上一行的结果即可；

• 如果$j$大于$0$而$i$等于$0$同理。

优化：如果到$grid[i][j]$的子矩阵元素和已经大于$k$，那么再往右和往下的更大子矩阵的和一定更大，可跳过。

• 时间复杂度$O(mn)$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-03-18 22:19:52
 */
class Solution {
public:
    int countSubmatrices(vector<vector<int>>& grid, int k) {
        int ans = 0;
        int n = grid.size(), m = grid[0].size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i && j) {
                    grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1];
                } else if (i) {
                    grid[i][j] += grid[i - 1][j];
                } else if (j) {
                    grid[i][j] += grid[i][j - 1];
                }
                ans += grid[i][j] <= k;
            }
        }
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源