[LeetCode]Ar598. 范围求和 II

🚩传送门：https://leetcode-cn.com/problems/range-addition-ii/

题目

给定一个初始元素全部为 0，大小为 的矩阵 M 以及在 M 上的一系列更新操作。操作用二维数组表示，每个操作用一个含有两个正整数 a 和 b 的数组表示，含义是将所有符合 0 <= i < a 以及 0 <= j < b的元素 M[i][j] 的值都增加 1。

在执行给定的一系列操作后，你需要返回矩阵中含有最大整数的元素个数。

解题思路：暴力 [Time Limit Exceeded]

最简单的方法是创建一个 的二维数组 ，对所有操作都逐一将范围内的元素加一，最后数一遍最大元素的数目。由于我们知道所有操作总是会影响到 (0,0)，所以元素 总是最大的。在所有操作执行完之后，我们数有多少个跟 一样大的元素就是答案。

复杂度分析

时间复杂度：，数组被更新 次， 是操作的次数，也就是 。

空间复杂度：，使用了大小为 的数组。

官方代码

public class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        //1.定义一个数组
        int[][] arr = new int[m][n];
        //2.依次遍历,ops是n行2列的数组
        for (int[] op: ops) {
            //3.按照操作对相应区域加1
            for (int i = 0; i < op[0]; i++) {
                for (int j = 0; j < op[1]; j++) {
                    arr[i][j] += 1;
                }
            }
        }
        int count = 0;
        //4.统计个数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] == arr[0][0])
                    count++;
            }
        }
        return count;
    }
}

解题思路：一次遍历 [Accepted]

不难发现其实就是个取区域交集的问题，最终值最大的区域一定是所有操作的交集区域。

所有操作都是在一个初始元素全为 0 的子矩阵上进行。每个矩形的左上角坐标都是 (0,0) 而右下角坐标是每个操作给出的坐标 (i,j)。最大元素是所有操作都会影响到的一个元素，下图是在初始 M 矩阵上执行了 2 次操作的一个示例图。

我们可以观察到最大元素会是两个操作对应矩阵的交集区域。我们还可以发现要求这块区域，我们不需要将操作区域一个一个加一，我们只需要记录交集区域的右下角即可。

这个角的计算方法为

最大元素的数目就是 。

复杂度分析

时间复杂度：，只需要遍历所有操作一次， 是操作的次数 。

空间复杂度：，不需要额外的数组空间。

官方代码

public class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        //1.依次遍历ops数组
        for (int[] op: ops) {
            //2.m记录最小行
            m = Math.min(m, op[0]);
            //3.n记录最小列
            n = Math.min(n, op[1]);
        }
        return m * n;
    }
}