Medium

题目描述

给你一个下标从 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 <= 10^9

解题思路

解题思路

这道题要求统计包含左上角元素且和小于等于k的子矩阵数量。关键观察是所有符合条件的子矩阵都必须以(0,0)为左上角。

核心思路：

  1. 由于子矩阵必须包含左上角元素，所有候选子矩阵的左上角都是(0,0)
  2. 对于右下角在(i,j)的子矩阵，我们需要快速计算从(0,0)到(i,j)的矩形区域和
  3. 使用二维前缀和可以在O(1)时间内计算任意矩形区域的和

算法步骤：

  1. 构建二维前缀和数组，prefixSum[i][j]表示从(0,0)到(i,j)的矩形区域和
  2. 遍历所有可能的右下角位置(i,j)
  3. 如果对应的前缀和小于等于k，则计数器加1
  4. 由于矩阵元素都非负，一旦某行的前缀和超过k，该行后续位置的前缀和也会超过k，可以提前跳出

优化： 当某个位置的前缀和超过k时，同行右侧的所有位置前缀和都会更大，可以直接跳出内层循环。

代码实现

class Solution {
public:
    int countSubmatrices(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        int count = 0;
        
        // 构建前缀和数组
        vector<vector<int>> prefixSum(m, vector<int>(n, 0));
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefixSum[i][j] = grid[i][j];
                if (i > 0) prefixSum[i][j] += prefixSum[i-1][j];
                if (j > 0) prefixSum[i][j] += prefixSum[i][j-1];
                if (i > 0 && j > 0) prefixSum[i][j] -= prefixSum[i-1][j-1];
                
                if (prefixSum[i][j] <= k) {
                    count++;
                } else {
                    break; // 当前行后续元素的前缀和都会更大
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def countSubmatrices(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        count = 0
        
        # 构建前缀和数组
        prefix_sum = [[0] * n for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                prefix_sum[i][j] = grid[i][j]
                if i > 0:
                    prefix_sum[i][j] += prefix_sum[i-1][j]
                if j > 0:
                    prefix_sum[i][j] += prefix_sum[i][j-1]
                if i > 0 and j > 0:
                    prefix_sum[i][j] -= prefix_sum[i-1][j-1]
                
                if prefix_sum[i][j] <= k:
                    count += 1
                else:
                    break  # 当前行后续元素的前缀和都会更大
        
        return count

public class Solution {
    public int CountSubmatrices(int[][] grid, int k) {
        int m = grid.Length, n = grid[0].Length;
        int count = 0;
        
        // 构建前缀和数组
        int[,] prefixSum = new int[m, n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefixSum[i, j] = grid[i][j];
                if (i > 0) prefixSum[i, j] += prefixSum[i-1, j];
                if (j > 0) prefixSum[i, j] += prefixSum[i, j-1];
                if (i > 0 && j > 0) prefixSum[i, j] -= prefixSum[i-1, j-1];
                
                if (prefixSum[i, j] <= k) {
                    count++;
                } else {
                    break; // 当前行后续元素的前缀和都会更大
                }
            }
        }
        
        return count;
    }
}

var countSubmatrices = function(grid, k) {
    const m = grid.length, n = grid[0].length;
    let count = 0;
    
    // 构建前缀和数组
    const prefixSum = Array(m).fill().map(() => Array(n).fill(0));
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            prefixSum[i][j] = grid[i][j];
            if (i > 0) prefixSum[i][j] += prefixSum[i-1][j];
            if (j > 0) prefixSum[i][j] += prefixSum[i][j-1];
            if (i > 0 && j > 0) prefixSum[i][j] -= prefixSum[i-1][j-1];
            
            if (prefixSum[i][j] <= k) {
                count++;
            } else {
                break; // 当前行后续元素的前缀和都会更大
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m×n)需要遍历整个矩阵构建前缀和，最坏情况下访问所有元素
空间复杂度O(m×n)需要额外的二维数组存储前缀和