598. 范圍求和 II
給定一個(gè)初始元素全部為 0排监，大小為 m*n 的矩陣 **M **以及在 **M **上的一系列更新操作叉谜。
操作用二維數(shù)組表示践樱，其中的每個(gè)操作用一個(gè)含有兩個(gè)正整數(shù) a 和 b 的數(shù)組表示，含義是將所有符合 0 <= i < a 以及 0 <= j < b 的元素 M[i][j] 的值都增加 1缕粹。
在執(zhí)行給定的一系列操作后稚茅，你需要返回矩陣中含有最大整數(shù)的元素個(gè)數(shù)。
示例 1:
輸入:
m = 3, n = 3
operations = [[2,2],[3,3]]
輸出: 4
解釋:
初始狀態(tài), 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 中有4個(gè)值為2的元素平斩。因此返回 4亚享。
注意:
- m 和 n 的范圍是 [1,40000]。
- a 的范圍是 [1,m]绘面，b 的范圍是 [1,n]欺税。
- 操作數(shù)目不超過(guò) 10000。
方法 2：一遍遍歷 [Accepted]
算法
正如題目描述揭璃，所有操作都是在一個(gè)初始元素全為 0 的子矩陣上進(jìn)行晚凿。每個(gè)矩形的左上角坐標(biāo)都是 (0,0)(0,0) 而右下角坐標(biāo)是 每個(gè)操作給出的坐標(biāo) (i,j)(i,j)。
最大元素是所有操作都會(huì)影響到的一個(gè)元素瘦馍，下圖是在初始 MM 矩陣上執(zhí)行了 2 次操作的一個(gè)示例圖歼秽。
從這張圖中，我們可以觀察到最大元素會(huì)是兩個(gè)操作對(duì)應(yīng)矩陣的交集區(qū)域情组。我們還可以發(fā)現(xiàn)要求這塊區(qū)域燥筷，我們不需要將操作區(qū)域一個(gè)一個(gè)加一，我們只需要記錄交集區(qū)域的右下角即可院崇。這個(gè)角的計(jì)算方法為 (x,y)=(min(op[0]),min(op[1]))肆氓， 其中min(op[i]) 表示所有操作的 op[i] 中的最小值。
這樣底瓣，最大元素的數(shù)目就是 x \times yx×y谢揪。
作者：LeetCode
鏈接：https://leetcode-cn.com/problems/range-addition-ii/solution/fan-wei-qiu-he-ii-by-leetcode/
來(lái)源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)濒持，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處键耕。
class Solution {
public:
int maxCount(int m, int n, vector<vector<int>>& ops) {
for (vector<int> op : ops) {
m = min(m, op[0]);
n = min(n, op[1]);
}
return m * n;
}
};
