LeetCode 0598.区间加法 II：最小值

devtools/2025/2/3 12:37:22/

【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 * 10⁴
0 <= ops.length <= 10⁴
ops[i].length == 2
1 <= a_i <= m
1 <= b_i <= n

解题方法：最小值

这道题很有意思，每次都是左上角的一小块加一。

最终最大整数的个数，不就是每次都被加一的那些元素么。

横纵坐标可以分开计算，对于横坐标，每次都覆盖掉的就是所有操作中在最小值；纵坐标同理。

文字描述不如代码描述，还不懂的话，看完代码就懂了。

时间复杂度 $O (l e n (o p s))$
空间复杂度 $O (1)$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-02-02 10:31:46* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-02 11:05:10*/
class Solution {
public:int maxCount(int m, int n, vector<vector<int>>& ops) {for (vector<int>& op : ops) {m = min(m, op[0]);n = min(n, op[1]);}return m * n;}
};

Python

'''
Author: LetMeFly
Date: 2025-02-02 11:06:10
LastEditors: LetMeFly.xyz
LastEditTime: 2025-02-02 11:07:44
'''
from typing import Listclass Solution:def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:for a, b in ops:m = min(m, a)n = min(n, b)return m * n

Java

/** @Author: LetMeFly* @Date: 2025-02-02 11:08:09* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-02 11:08:11*/
class Solution {public int maxCount(int m, int n, int[][] ops) {for (int[] op : ops) {m = Math.min(m, op[0]);n = Math.min(n, op[1]);}return m * n;}
}

Go

/** @Author: LetMeFly* @Date: 2025-02-02 11:09:24* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-02 11:10:27*/
package mainfunc min_RA2(m, n int) int {if m < n {return m}return n
}func maxCount(m int, n int, ops [][]int) int {for _, op := range ops {m = min_RA2(m, op[0])n = min_RA2(n, op[1])}return m * n
}