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

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
public:
    int countSubmatrices(vector<vector<int>>& grid, int k) {
        int res = 0, m = grid.size(), n = grid[0].size();
        vector<vector<int>> prefix(m + 1, vector<int>(n + 1));

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefix[i + 1][j + 1] = prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j] + grid[i][j];
                res += prefix[i + 1][j + 1] <= k;
            }
        }

        return res;
    }
};