問題（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.
大意：
給出一個(gè)m*n的矩陣M，初始化都是0牙咏，對其進(jìn)行很多操作量窘。
操作由二維數(shù)組表示，每個(gè)操作由有兩個(gè)整數(shù)a和b組成的數(shù)組表示，其表示矩陣中所有 0 <= i < a 和 0 <= j < b 的M[i][j]都要加1。
你需要計(jì)算并返回經(jīng)過所有操作后矩陣中最大數(shù)的個(gè)數(shù)。
例1：
輸入：
m = 3, n = 3
operations = [[2,2],[3,3]]
輸出：4
解釋：
初始時(shí)镇辉，M =
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]執(zhí)行 [2,2], M =
[[1, 1, 0],
[1, 1, 0],
[0, 0, 0]]執(zhí)行 [3,3], M =
[[2, 2, 1],
[2, 2, 1],
[1, 1, 1]]所以M中最大的整數(shù)是2，在M中有四個(gè)贴捡，所以返回4忽肛。
注意：
- m和n的范圍是[1,40000]。
- a的范圍是[1,m]烂斋，b的范圍是[1,n]屹逛。
- 操作的尺寸不超過10000。
思路：
乍看之下有點(diǎn)麻煩源祈，每次操作都要變化矩陣煎源，但實(shí)際上因?yàn)槊看尾僮鞫际且粋€(gè)從左上角開始的矩形區(qū)域，所以實(shí)際上每次都會保證最小的操作范圍內(nèi)的數(shù)加一香缺，也就是說我們只用遍歷操作，找到最小的a和b歇僧，那么他們下面的區(qū)域一定每次操作都進(jìn)行了加一图张，一定是最大的數(shù)，因此計(jì)算其面積就可以了诈悍。
當(dāng)然如果什么都不操作祸轮，那么矩陣中最大數(shù)就是0，因此0的數(shù)量就是矩陣的面積侥钳，所以初始化時(shí)正好就是矩陣的長寬适袜。
代碼（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
