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

LeetCode题练习与总结：区间加法 Ⅱ -- 598

article 2025/3/10 4:22:18

一、题目描述

给你一个 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。而子矩阵的大小由操作数组的每一项决定。因此，最大的整数出现在操作数组中所有子矩阵交集的区域内。

由于每次操作都是对左上角的子矩阵进行操作，所以交集区域一定是左上角的一个小矩阵。这个小矩阵的左上角坐标是(0, 0)，而右下角坐标是操作数组中所有ai和bi的最小值。

因此，我们可以通过遍历操作数组，找到所有ai和bi的最小值，然后计算交集区域的面积，即最小值ai和bi的乘积。

三、具体代码

class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        // 初始化最小值为矩阵的尺寸
        int minRow = m;
        int minCol = n;

        // 遍历操作数组，找到最小的ai和bi
        for (int[] op : ops) {
            minRow = Math.min(minRow, op[0]);
            minCol = Math.min(minCol, op[1]);
        }

        // 计算交集区域的面积，即最大整数的个数
        return minRow * minCol;
    }
}

在这段代码中，我们初始化minRow和minCol为矩阵的初始尺寸。然后遍历操作数组，更新minRow和minCol为遍历过程中遇到的最小ai和bi。最后，返回minRow和minCol的乘积，即为矩阵中最大整数的个数。

四、时间复杂度和空间复杂度

1. 时间复杂度

初始化最小值：这一步是常数时间操作，时间复杂度为 O(1)。
遍历操作数组：这一步需要遍历整个操作数组一次。如果操作数组的长度为 k，那么这一步的时间复杂度为 O(k)，因为我们需要对每个操作数组的元素执行常数时间的操作（即计算最小值）。
计算交集区域的面积：这一步是常数时间操作，时间复杂度为 O(1)。

综合以上步骤，总的时间复杂度是 O(k)，其中 k 是操作数组的长度。

2. 空间复杂度

变量存储：在代码中，我们使用了几个整型变量（minRow, minCol）来存储中间结果，这些变量占用的空间是常数，因此空间复杂度为 O(1)。
输入数据：输入数据包括矩阵的行数 m、列数 n 和操作数组 ops。这些数据的空间占用取决于输入的大小，但它们不是由算法本身分配的，因此不计入算法的空间复杂度。

综上所述，该算法的空间复杂度为 O(1)，因为它使用了固定数量的额外空间，与输入数据的大小无关。

五、总结知识点

类定义：
- class 关键字用于定义一个类。
- 类名 Solution 表示这是一个解决特定问题的类。
方法定义：
- public 关键字表示该方法可以被类外部访问。
- int 表示该方法返回一个整数类型的结果。
- 方法名 maxCount 表示该方法用于计算最大计数。
- 方法的参数列表 (int m, int n, int[][] ops) 表示该方法接受三个参数：整数 m 和 n，以及一个二维整数数组 ops。
变量声明和初始化：
- int minRow = m; 和 int minCol = n; 用于声明并初始化两个整型变量，它们用于存储最小行数和最小列数。
循环结构：
- for 循环用于遍历二维数组 ops。
- 增强型 for 循环 (for (int[] op : ops)) 用于逐个处理数组中的每个元素，其中 op 是当前操作的数组。
数学运算：
- Math.min 方法用于计算两个整数中的最小值。
- * 运算符用于执行乘法运算。
数组访问：
- op[0] 和 op[1] 用于访问操作数组 op 中的第一个和第二个元素，这些元素分别代表操作影响的行数和列数。