问题描述给你一个下标从0开始的整数矩阵grid和一个整数k。返回包含grid左上角元素、元素和小于或等于k的子矩阵的数目。子矩阵是指矩阵中连续若干行、连续若干列所构成的矩形区域。这里要求子矩阵必须包含左上角(0,0)位置即子矩阵的左上角固定为(0,0)右下角可以是任意合法的(i,j)。示例 1输入grid [[7,6,3],[6,6,1]], k 18输出4解释如下图所示只有 4 个子矩阵满足条件右下角分别为 (0,0), (0,1), (0,2), (1,0)它们的和分别是 7, 13, 16, 13均 ≤ 18。注意 (1,1) 对应子矩阵和 766625 18不计数。763661示例 2输入grid [[7,2,9],[1,5,0],[2,6,6]], k 20输出6解释所有左上角为 (0,0) 的子矩阵中有 6 个和 ≤ 20右下角分别为 (0,0),(0,1),(0,2),(1,0),(1,1),(2,0)其余如 (2,1) 子矩阵和 721526 23 20不计数。729150266提示m grid.lengthn grid[i].length1 n, m 10000 grid[i][j] 10001 k 10^9问题分析题目要求子矩阵必须包含grid[0][0]也就是说子矩阵的左上角固定为原点(0,0)。那么一个子矩阵完全由它的右下角坐标(i,j)决定其中0 ≤ i m,0 ≤ j n该子矩阵覆盖了从第 0 行到第 i 行、第 0 列到第 j 列的所有元素。因此问题转化为统计所有可能的右下角(i,j)使得从(0,0)到(i,j)的矩形内所有元素之和≤ k。思路与算法直接枚举所有i和j并快速计算该子矩阵的和是解决本题的核心。二维前缀和prefix sum是处理此类矩形区域求和的经典工具。二维前缀和定义设pre[i][j]表示从(0,0)到(i-1,j-1)构成的子矩阵的和常用 1-based 下标避免边界判断但为了方便我们采用 0-based 下标并定义prefix[i][j] sum_{r0}^{i} sum_{c0}^{j} grid[r][c]即从(0,0)到(i,j)的矩形和。根据递推关系prefix[i][j] grid[i][j] (prefix[i-1][j] if i0 else 0) (prefix[i][j-1] if j0 else 0) - (prefix[i-1][j-1] if i0 and j0 else 0)这样我们可以在 O(m*n) 时间内计算出所有前缀和。统计答案计算出所有prefix[i][j]后直接遍历每个(i,j)判断prefix[i][j] ≤ k统计满足条件的个数。由于grid[i][j] ≥ 0前缀和矩阵是非递减的即向右或向下移动时和不会减少但这并不影响我们直接遍历所有可能。时间复杂度 O(m*n)完全满足题目约束最大 10^6 量级。代码实现fromtypingimportListclassSolution:defcountSubmatrices(self,grid:List[List[int]],k:int)-int:m,nlen(grid),len(grid[0])# 二维前缀和数组大小与原矩阵相同prefix[[0]*nfor_inrange(m)]ans0foriinrange(m):row_sum0# 用于累加当前行的前缀和forjinrange(n):row_sumgrid[i][j]# 当前 (i,j) 的前缀和 上一行同一列的前缀和 当前行的累加和# 如果 i 0则上一行前缀和为0prefix[i][j](prefix[i-1][j]ifi0else0)row_sumifprefix[i][j]k:ans1returnans代码说明我们并没有显式构建完整的二维前缀和矩阵可以只用一维数组滚动优化但为了清晰这里使用了完整二维数组。内层循环用row_sum动态维护从(i,0)到(i,j)的累加和结合上一行同一列的前缀和即可得到prefix[i][j]。时间复杂度 O(mn)空间复杂度 O(mn)可优化至 O(n)。示例模拟示例1grid [7, 6, 3] [6, 6, 1]计算前缀和矩阵i0:j0: prefix[0][0] 7 → 7 ≤ 18 → ans1j1: row_sum7613, prefix[0][1]13 ≤ 18 → ans2j2: row_sum13316, prefix[0][2]16 ≤ 18 → ans3i1:j0: row_sum6, prefix[1][0]prefix[0][0]613 ≤ 18 → ans4j1: row_sum6612, prefix[1][1]prefix[0][1]1225 18 → 不计j2: row_sum12113, prefix[1][2]prefix[0][2]1329 18 → 不计最终 ans4。示例2grid [7, 2, 9] [1, 5, 0] [2, 6, 6]计算过程略最终得到6个符合条件的右下角(0,0),(0,1),(0,2),(1,0),(1,1),(2,0)。复杂度分析时间复杂度O(m*n)。需要遍历矩阵每个元素一次计算前缀和并判断。空间复杂度O(mn) 用于存储前缀和矩阵。可以优化至 O(n)只保留上一行前缀和但对本题规模10^6来说 O(mn) 也是完全可以接受的约 1e6 个整数内存约 8MB。进阶思考为什么可以直接遍历所有右下角因为左上角固定子矩阵与右下角一一对应无需额外枚举。如果 grid 中包含负数怎么办题目已保证非负所以前缀和单调不减不会出现回退遍历即可。若含负数则需要更复杂的双指针或二分但本题不涉及。能否优化遍历顺序提前终止由于前缀和非负当某一行第一个前缀和已经 k 时该行后续列都会更大可以提前终止该行的遍历。代码中可以加入if prefix[i][0] k: continue来小优化但 O(m*n) 已经足够快。总结本题是二维前缀和的直接应用关键点在于理解“包含左上角”意味着子矩阵由右下角唯一确定。通过计算二维前缀和并统计即可轻松得到答案。对于初学者这是理解二维前缀和与矩阵求和的很好练习题。希望这篇题解对你有所帮助如果有任何疑问欢迎在评论区交流。