区间加法 II

标签: 数组 数学

难度: Easy

给你一个 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

Submission

运行时间: 22 ms

内存: 17.4 MB

class Solution:
    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
        if not ops:return m*n
        L1,L2=[],[]
        for f in ops:
            L1.append(f[0])
            L2.append(f[1])
        return min(L1)*min(L2)

Explain

这个题解的思路是利用题目给定操作的特点来简化计算。根据题意，所有满足 0 <= x < ai 和 0 <= y < bi 的格子都会加 1。因此，经过所有操作后，最终矩阵中最大的整数一定出现在所有操作的交集区域内。我们只需要找出所有操作中最小的 ai 和最小的 bi，它们的乘积就是最大整数的个数。如果 ops 为空，说明没有任何操作，此时矩阵中所有元素都为0，最大整数的个数就是 m*n。

时间复杂度: O(len(ops))

空间复杂度: O(len(ops))

class Solution:
    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
        # 如果没有任何操作，返回矩阵的面积
        if not ops:
            return m * n
        
        L1, L2 = [], []
        for f in ops:
            # 将每个操作的 ai 和 bi 分别存入 L1 和 L2
            L1.append(f[0])
            L2.append(f[1])
        
        # 返回所有操作中最小的 ai 和最小的 bi 的乘积
        return min(L1) * min(L2)

Explore

使用两个列表 L1 和 L2 来存储所有 ai 和 bi 的值可能是出于代码编写的简便性考虑。这种方式使得代码更为直观和易于理解，特别是对于那些刚开始学习算法的学生。然而，这种方法确实存在效率上的不足，因为它需要额外的空间来存储这些值，并且在获取最小值时需要遍历整个列表。直接在遍历过程中维护最小值（使用变量存储当前遇到的最小 ai 和 bi）会更加高效，因为它无需额外的存储空间，同时还能减少计算时间。

确实应该考虑 m 或 n 为 0 的情况。如果 m 或 n 任何一个为 0，那么矩阵的面积为 0（因为矩阵的一维或两维不存在实际的格子）。在这种情况下，无论进行多少次操作，矩阵中的整数最大数目都应该是 0，因为实际上不存在任何格子可以增加值。因此，如果 m 或 n 为 0，正确的返回值应该是 0。

将每次操作的 ai 和 bi 添加到列表中确实会在操作数很大时影响性能，主要是因为这种实现方式需要更多的内存并且在寻找最小值时增加了计算量。更优的方法是在遍历 ops 的过程中直接维护两个变量，分别记录遇到的最小 ai 和最小 bi。这样可以避免使用额外的存储空间，并且可以在遍历一次过程中直接得到结果，从而提高算法的效率和性能。