3359. 查找最大元素不超过 K 的有序子矩阵 🔒
题目描述
给定一个大小为 m x n 的二维矩阵 grid。同时给定一个 非负整数 k。
返回满足下列条件的 grid 的子矩阵数量：
- 子矩阵中最大的元素 小于等于
k。 - 子矩阵的每一行都以 非递增 顺序排序。
矩阵的子矩阵 (x1, y1, x2, y2) 是通过选择所有满足 x1 <= x <= x2 且 y1 <= y <= y2 的 grid[x][y] 元素组成的矩阵。
示例 1：
输入：grid = [[4,3,2,1],[8,7,6,1]], k = 3
输出：8
解释：
8 个子矩阵分别是：
[[1]][[1]][[2,1]][[3,2,1]][[1],[1]][[2]][[3]][[3,2]]
示例 2：
输入：grid = [[1,1,1],[1,1,1],[1,1,1]], k = 1
输出：36
解释：
矩阵中有 36 个子矩阵。所有子矩阵的最大元素都等于 1。
示例 3：
输入：grid = [[1]], k = 1
输出：1
提示：
1 <= m == grid.length <= 1031 <= n == grid[i].length <= 1031 <= grid[i][j] <= 1091 <= k <= 109
解法
方法一
1 | |
1 | |
1 | |
1 | |