【Leetcode Daily】3070元素和小于等于k的子矩阵的数目

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个二维数组，找到其中所有左上角就是 0，0 的子矩阵之和小于等于给定数字 k 的个数。

思路分享

• 按照经典的二维前缀和求的同时，统计当前前缀和值是否小于等于k即可。如何计算这个二位前缀和不再赘述。

  https://leetcode.cn/problems/count-submatrices-with-top-left-element-and-sum-less-than-k/solutions/2664654/mo-ban-er-wei-qian-zhui-he-pythonjavacgo-fnk1/

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def countSubmatrices(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        f = [[0]*(n+1) for _ in range(m+1)]
        ans = 0
        for i in range(m):
            for j in range(n):
                f[i+1][j+1] = f[i][j+1] + f[i+1][j] - f[i][j] + grid[i][j]
                if f[i+1][j+1] <= k:
                    ans += 1
        return ans