598. 区间加法 II

🟢   🔖  数组 数学  🔗 力扣 LeetCode

题目

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 。矩阵初始化时所有的单元格都为 0 。ops[i] = [ai, bi] 意味着当所有的 0 <= x < ai 和 0 <= 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 数组，对 a 和 b 分别取最小值，得到操作后的最小行 minRow 和最小列 minCol。
   • 矩形网格的最大值区域即为大小为 minRow × minCol 的矩形区域。

3. 特殊情况

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

复杂度分析

• 时间复杂度：O(k)，其中 k 是 ops 的长度，遍历 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	区间加法 🔒		数组 前缀和	🟠	🀄️ 🔗
2718	查询后矩阵的和		数组 哈希表	🟠	🀄️ 🔗