[LeetCode] 每日一题 598. 区间加法 II
题目链接
题目描述
给你一个 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
解题思路
本题的目标是计算一个 m x n
的矩阵在执行一系列操作后,矩阵中最大整数的个数。矩阵初始时所有单元格都为 0,每次操作会将一个子矩阵的元素加 1。
关键思路:
每次操作都定义了一个子矩阵的右下角
ai, bi
,即对0 <= x < ai
和0 <= y < bi
的位置进行加 1 操作。因为所有的操作都会影响到矩阵的一部分,我们的任务就是找出最后被操作的最大区域。在所有操作后,矩阵中最大整数的个数显然是矩阵的左上角(即
min(ai)
和min(bi)
所定义的区域),这个区域中的每个位置都受到了所有操作的影响,并且被加了最多次。
因此,只需要通过对所有操作求出 ai
和 bi
的最小值(即 minX
和 minY
),最终矩阵中的最大整数的个数就是 minX * minY
。
代码实现
class Solution {
public int maxCount(int m, int n, int[][] ops) {
int minX = m;
int minY = n;
for (int[] op : ops) {
minX = Math.min(minX, op[0]);
minY = Math.min(minY, op[1]);
}
return minX * minY;
}
}
复杂度分析
时间复杂度:O(k),其中
k
是操作数组ops
的长度。我们需要遍历所有的操作来求最小的ai
和bi
。空间复杂度:O(1),只使用了几个额外的变量来存储最小值,空间复杂度是常数级别。
总结
本题的关键是理解操作的影响范围,通过找到所有操作中最小的 ai
和 bi
,可以确定矩阵中最大整数的区域大小。由于操作并不改变原始矩阵的形状,求解过程非常简洁,时间复杂度仅为 O(k),非常高效。通过最小值的计算,我们能快速得出矩阵中最大整数的个数
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。