leetcode 598. Range Addition II 范围内的操作 + 遍历即可

小鱼儿 2022-06-03 04:46 184阅读 0赞

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.

本题题意看起来十分的复杂，其实十分的简单，只需要遍历ops的值来更新m和n，求最小值，这个就是最终的最大数的边界

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int maxCount(int m, int n, vector<vector<int>>& ops)
        {
            for (vector<int> a :ops)
            {
                m = min(m, a[0]);
                n = min(n, a[1]);
            }
            return m*n;
        }
    };