LeetCode笔记：598. Range Addition II

问题（Easy）：

Given an m * n matrix M initialized with all 0's and several update operations. Operations are represented by a 2D array, and each operation is represented by an array with two positive integers a and b, which means M[i][j] should be added by one for all 0 <= i < a and 0 <= j < b. You need to count and return the number of maximum integers in the matrix after performing all the operations. Example 1: Input: m = 3, n = 3 operations = [[2,2],[3,3]] Output: 4 Explanation: Initially, M = [[0, 0, 0], [0, 0, 0], [0, 0, 0]] After performing [2,2], M = [[1, 1, 0], [1, 1, 0], [0, 0, 0]] After performing [3,3], M = [[2, 2, 1], [2, 2, 1], [1, 1, 1]] So the maximum integer in M is 2, and there are four of it in M. So return 4. Note:

1. The range of m and n is [1,40000].
2. The range of a is [1,m], and the range of b is [1,n].
3. The range of operations size won't exceed 10,000.

大意：

给出一个m*n的矩阵M，初始化都是0，对其进行很多操作。 操作由二维数组表示，每个操作由有两个整数a和b组成的数组表示，其表示矩阵中所有 0 <= i < a 和 0 <= j < b 的M[i][j]都要加1。 你需要计算并返回经过所有操作后矩阵中最大数的个数。 例1： 输入： m = 3, n = 3 operations = [[2,2],[3,3]] 输出：4 解释： 初始时，M = [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 执行 [2,2], M = [[1, 1, 0], [1, 1, 0], [0, 0, 0]] 执行 [3,3], M = [[2, 2, 1], [2, 2, 1], [1, 1, 1]] 所以M中最大的整数是2，在M中有四个，所以返回4。 注意：

1. m和n的范围是[1,40000]。
2. a的范围是[1,m]，b的范围是[1,n]。
3. 操作的尺寸不超过10000。

思路：

乍看之下有点麻烦，每次操作都要变化矩阵，但实际上因为每次操作都是一个从左上角开始的矩形区域，所以实际上每次都会保证最小的操作范围内的数加一，也就是说我们只用遍历操作，找到最小的a和b，那么他们下面的区域一定每次操作都进行了加一，一定是最大的数，因此计算其面积就可以了。

当然如果什么都不操作，那么矩阵中最大数就是0，因此0的数量就是矩阵的面积，所以初始化时正好就是矩阵的长宽。

代码（C++）：

class Solution {
public:
    int maxCount(int m, int n, vector<vector<int>>& ops) {
        int mina = m, minb = n;
        int len = ops.size();
        for (int i = 0; i < len; i++) {
            vector<int> one = ops[i];
            mina = min(mina, one[0]);
            minb = min(minb, one[1]);
        }
        return mina*minb;
    }
};

合集：https://github.com/Cloudox/LeetCode-Record