TNotes.leetcode

Appearance

0598. 区间加法 II【简单】

0598. 区间加法 II【简单】 ​

1. 📝 题目描述 ​

给你一个 m x n 的矩阵 M 和一个操作数组 op。矩阵初始化时所有的单元格都为 0。ops[i] = [ai, bi] 意味着当所有的 0 <= x < ai 和 0 <= y < bi 时， M[x][y] 应该加 1。

在 执行完所有操作后，计算并返回 矩阵中最大整数的个数。

示例 1：

img

txt
输入: m = 3, n = 3，ops = [[2,2],[3,3]]
输出: 4
解释: M 中最大的整数是 2, 而且 M 中有4个值为2的元素。因此返回 4。

示例 2：

txt
输入: m = 3, n = 3, ops = [[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3]]
输出: 4

示例 3：

txt
输入: m = 3, n = 3, ops = []
输出: 9

提示：

  • 1 <= m, n <= 4 * 10^4
  • 0 <= ops.length <= 10^4
  • ops[i].length == 2
  • 1 <= ai <= m
  • 1 <= bi <= n

2. 🎯 s.1 - 暴力解法 ​

js
/**
 * @param {number} m
 * @param {number} n
 * @param {number[][]} ops
 * @return {number}
 */
var maxCount = function (m, n, ops) {
  // 如果没有操作，整个矩阵的值都是0，最大值个数就是m*n
  if (ops.length === 0) {
    return m * n
  }

  // 找到所有操作中最小的行数和列数
  let minRow = m
  let minCol = n

  for (let op of ops) {
    minRow = Math.min(minRow, op[0])
    minCol = Math.min(minCol, op[1])
  }

  // 最大值的个数就是这个交集区域的面积
  return minRow * minCol
}
  • 时间复杂度：O(k)，其中 k 为 ops 的长度，需要遍历所有操作以找到最小行列。
  • 空间复杂度：O(1)，只使用了常数级变量存储最小行列值。
  • 关键点：
    • 所有操作都是从 (0,0) 开始的矩形区域
    • 最大值一定出现在所有操作都覆盖的区域
    • 这个区域就是所有操作矩形的交集
  • 算法思路：
    1. 核心思想：所有操作都从 (0,0) 开始，所以重叠区域就是所有操作矩形的交集
    2. 交集计算：交集区域的边界由所有操作中最小的行数(minRow)和列数(minCol)决定
    3. 边界情况：当没有操作时，整个矩阵的值都为 0，所以返回整个矩阵的面积m * n

Discussions