跳至主要內容

598. 区间加法 II


598. 区间加法 II

🟢   🔖  数组 数学  🔗 力扣open in new window LeetCodeopen in new window

题目

You are given an m x n matrix M initialized with all 0's and an array of operations ops, where ops[i] = [ai, bi] means M[x][y] should be incremented by one for all 0 <= x < ai and 0 <= y < bi.

Count and return the number of maximum integers in the matrix after performing all the operations.

Example 1:

Input: m = 3, n = 3, ops = [[2,2],[3,3]]

Output: 4

Explanation: The maximum integer in M is 2, and there are four of it in M. So return 4.

Example 2:

Input: 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]]

Output: 4

Example 3:

Input: m = 3, n = 3, ops = []

Output: 9

Constraints:

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

题目大意

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

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

示例 1:

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

输出: 4

解释: M 中最大的整数是 2, 而且 M 中有 4 个值为 2 的元素。因此返回 4。

示例 2:

输入: 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:

输入: 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

解题思路

  1. 值最大的区域

    • 对于每次操作 ops[i] = [a, b],会对矩形 (0,0)(a-1, b-1) 的区域加 1。
    • 因此,值最大的区域会被所有操作重叠,实际是所有操作中矩形的最小范围交集
  2. 如何计算最小范围交集

    • 遍历 ops 数组,对 ab 分别取最小值,得到操作后的最小行 minRow 和最小列 minCol
    • 矩形网格的最大值区域即为大小为 minRow × minCol 的矩形区域。
  3. 特殊情况

    • 如果 ops 是空数组,没有任何操作,值最大的网格区域就是整个矩形 m × n

复杂度分析

  • 时间复杂度O(k),其中 kops 的长度,遍历 ops 一次。
  • 空间复杂度O(1),只使用了常量空间。

代码

/**
 * @param {number} m
 * @param {number} n
 * @param {number[][]} ops
 * @return {number}
 */
var maxCount = function (m, n, ops) {
	let minRow = m; // 初始为矩阵行数
	let minCol = n; // 初始为矩阵列数

	// 遍历操作,计算最小行数和列数
	for (let [a, b] of ops) {
		minRow = Math.min(minRow, a);
		minCol = Math.min(minCol, b);
	}

	// 最大值区域的网格数量
	return minRow * minCol;
};

相关题目

题号标题题解标签难度力扣
370区间加法 🔒数组 前缀和🟠🀄️open in new window 🔗open in new window
2718查询后矩阵的和数组 哈希表🟠🀄️open in new window 🔗open in new window