当前位置：首页 > article >正文

区间加法 II - 解题思路与代码解析

article 2025/2/3 6:07:48

区间加法 II - 解题思路与代码解析

问题描述

给定一个 m x n 的矩阵 M，矩阵初始时所有单元格为 0。我们有一系列操作，每个操作都是一个二元组 [ai, bi]，表示在矩阵中对前 ai 行和前 bi 列的所有元素加 1。

我们的任务是在执行所有操作后，计算并返回矩阵中最大整数的个数。

示例

示例 1：

输入：

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

输出：

解释：执行完操作后，矩阵中的最大整数是 2，并且矩阵中有 4 个 2。

示例 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]]

输出：

示例 3：

输入：

m = 3
n = 3
ops = []

输出：

解释：没有操作时，所有元素都为 0，最大值为 0，矩阵的所有元素都是最大值。

解题思路

1. 矩阵操作的本质

矩阵的每一次操作都是对其一部分区域（前 ai 行和前 bi 列）进行加 1。多个操作可能会影响不同的矩阵区域。我们要找出所有操作中最小的 ai 和 bi，因为这些值决定了最大整数的个数。

2. 关键点分析

每次操作 [ai, bi] 都对矩阵的前 ai 行和前 bi 列的所有元素加 1。
我们只关心矩阵中最小的 ai 和 bi，因为这些值决定了矩阵中最大值出现的位置。
由于操作对矩阵的影响是逐步叠加的，因此所有操作后，矩阵中的最大值出现在矩阵的最小区域。

3. 解决方案

如果没有任何操作，矩阵的所有元素仍然为 0，所以返回矩阵的元素总数 m * n。
如果有操作，遍历所有操作，找到最小的 ai 和 bi，这代表矩阵中被操作过的最小区域。最大值的个数就是这个区域的面积，即 min(ai) * min(bi)。

4. 时间复杂度

由于我们只需要遍历 ops 数组一次，时间复杂度为 O(k)，其中 k 是操作的数量。

5. 空间复杂度

只使用了常数空间，所以空间复杂度为 O(1)。

代码实现

from typing import List

class Solution:
    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
        # 如果没有任何操作，矩阵中的元素都为 0，最大值是 0
        if not ops:
            return m * n
        
        # 初始时设置 a 和 b 为一个非常大的值
        a, b = 2e9, 2e9
        
        # 遍历操作数组，找出最小的 ai 和 bi
        for op in ops:
            a = min(a, op[0])
            b = min(b, op[1])
        
        # 最大值的个数就是最小区域的面积
        return int(a * b)

代码解析

初始化 a 和 b：我们设置 a 和 b 为非常大的值 2e9，保证在第一次遍历时，操作中的 ai 和 bi 能够更新它们的值。
遍历操作数组：通过遍历操作数组，我们在每一步都更新 a 和 b，使它们分别为最小的 ai 和 bi。这两个值决定了矩阵中最大值出现的区域。
计算结果：矩阵中最大值的个数就是最小区域的面积，即 a * b。
特殊情况：如果操作数组为空，直接返回 m * n，因为矩阵中所有元素都为 0。