元素和小于等于 k 的子矩阵的数目1

题目讲解

容斥原理

prefix[a][b] 表示从左上角 (0,0) 到 (a-1,b-1) 的矩形和.

$$ prefix[i-1][j] = \sum_{x=0}^{i-2} \sum_{y=0}^{j-1} grid[x][y] $$

具体流程

代码

c++
python
java
class Solution:
    def countSubmatrices(self, grid, k):
        m, n = len(grid), len(grid[0])
        # 初始化一个 二维数组（矩阵），用来存储前缀和.
        prefix = [[0] * (n + 1) for _ in range(m + 1)]
        res = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                prefix[i][j] = (grid[i-1][j-1] +
                                prefix[i-1][j] +
                                prefix[i][j-1] -
                                prefix[i-1][j-1])
                if prefix[i][j] <= k:
                    res += 1
        return res

链接

  1. 元素和小于等于 k 的子矩阵的数目https://leetcode.cn/problems/count-submatrices-with-top-left-element-and-sum-less-than-k/description/ ↩︎