598.区间加法 II:最小值
【LetMeFly】598.区间加法 II:最小值
力扣题目链接:https://leetcode.cn/problems/range-addition-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 * 104
0 <= ops.length <= 104
ops[i].length == 2
1 <= ai <= m
1 <= bi <= n
解题方法:最小值
这道题很有意思,每次都是左上角的一小块加一。
最终最大整数的个数,不就是每次都被加一的那些元素么。
横纵坐标可以分开计算,对于横坐标,每次都覆盖掉的就是所有操作中在最小值;纵坐标同理。
文字描述不如代码描述,还不懂的话,看完代码就懂了。
- 时间复杂度$O(len(ops))$
- 空间复杂度$O(1)$
AC代码
C++
1 |
|
Python
1 |
|
Java
1 |
|
Go
1 |
|
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/145418564
598.区间加法 II:最小值
https://blog.letmefly.xyz/2025/02/02/LeetCode 0598.区间加法II/