Leetcode 598. 区间加法 II

原题链接：Leetcode 598. Range Addition II

You are given an m x n matrix M initialized with all 0’s and an array of operations ops, where ops[i] = [ai, bi] means M[x][y] should be incremented by one for all 0 <= x < ai and 0 <= y < bi.

Count and return the number of maximum integers in the matrix after performing all the operations.

Example 1:

Input: m = 3, n = 3, ops = [[2,2],[3,3]]
Output: 4

Explanation: The maximum integer in M is 2, and there are four of it in M. So return 4.

Example 2:

Input: 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]]
Output: 4

Example 3:

Input: m = 3, n = 3, ops = []
Output: 9

Constraints:

• 1 <= m, n <= 4 * 10⁴
• 0 <= ops.length <= 10⁴
• ops[i].length == 2
• 1 <= ai <= m
• 1 <= bi <= n

题目大意：

有一个m行n列的矩阵M，初始元素均为0。再给定一个二维数组ops.
对于ops中的元素，假设为 [a, b] ， 那么他对应的操作就是将矩阵M中，以 M[0][0] 为左上角， M[a][b] 为右下角的部分元素均加上1。
最终需要返回矩阵M中元素最大值的元素个数。

方法一：简单模拟：求交集

思路：

ops中的操作可以看做是一个个的小矩阵，每次对小矩阵中的元素进行加1操作。
那么什么情况会使得某一元素成为最大元素呢？那就是每次操作他都在对应的矩阵中。
那么可以对每次矩阵求交集，交集中的元素个数就是需要的答案。

C++ 代码：

class Solution {
public:
    int maxCount(int m, int n, vector<vector<int>>& ops) {
        // x交集的行数 y交集的列数
        int x = m, y = n;
        for(const auto& op: ops){
            x = min(x, op[0]);
            y = min(y, op[1]);
        }

        return x * y;
    }
};

复杂度分析：

• 时间复杂度：O(k)，k是ops中操作的个数
• 空间复杂度：O(1)