598. 范圍求和 II

給定一個初始元素全部為?0，大小為 m*n 的矩陣?M?以及在?M?上的一系列更新操作。

操作用二維數組表示，其中的每個操作用一個含有兩個正整數?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個值為2的元素。因此返回 4。

注意:

• m 和 n 的范圍是?[1,40000]。
• a 的范圍是 [1,m]，b 的范圍是 [1,n]。
• 操作數目不超過 10000。

解題思路

因為每個操作是將所有符合?0 <= i < a 以及 0 <= j < b 的元素?M[i][j]?的值都增加 1。

因此，對于每個操作我們可以看成是在原矩陣M的基礎上覆蓋一層矩陣，并且所有覆蓋矩陣都是從原矩陣的左上角開始覆蓋的，而矩陣中含有最大整數的元素個數，可以看成是矩陣M被覆蓋次數最多的那個部分，因此，我們只需要取出每個操作中最小的正整數a和b，就是被覆蓋次數最多的那個部分，他們的面積就算最大整數的元素個數。

代碼

class Solution {
public:int maxCount(int m, int n, vector<vector<int>>& ops) {if (ops.size()==0) return m*n;int l(0x7fffffff),r(0x7fffffff);for (auto  op:ops){l=min(op[0],l);r=min(op[1],r);}return l*r;}
};

復雜度分析

• 時間復雜度：O(k)，其中?k?是數組?$\text{ops}$?的長度。
• 空間復雜度：O(1)。