问题（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:
- The range of m and n is [1,40000].
- The range of a is [1,m], and the range of b is [1,n].
- 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。
注意：
- m和n的范围是[1,40000]。
- a的范围是[1,m]，b的范围是[1,n]。
- 操作的尺寸不超过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
