范围求和（算法题）

题目：给你一个 m x n 的矩阵 M ，初始化时所有的 0 和一个操作数组 op ，其中 ops[i] = [ai, bi] 意味着当所有的 0 <= x < ai 和 0 <= y < bi 时， Mx 应该加 1。

在 执行完所有操作后 ，计算并返回 矩阵中最大整数的个数 。

示例1：

输入: m = 3, n = 3，ops = [[2,2],[3,3]]
输出: 4
解释: M 中最大的整数是 2, 而且 M 中有4个值为2的元素。因此返回 4。

        

          
        
        
        

          

          AI 代码解读
        
      
      

示例2：

输入: m = 3, n = 3, ops = [[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3]]
输出: 4

        

          
        
        
        

          

          AI 代码解读
        
      
      

提示：

• 1 <= m, n <= 4 * 104
• 0 <= ops.length <= 104
• ops[i].length == 2
• 1 <= ai <= m
• 1 <= bi <= n

思路

按照题目的要求，对于每一次操作，给定 (a,b)，我们会将矩阵中所有满足 0≤i<a以及 0≤j<b的位置 (i,j)全部加上 1。由于 a,b均为正整数，那么 (0,0) 总是满足上述条件，并且最终位置 (0,0) 的值就等于操作的次数。详细可以参考598题。

class Solution {
public:
    int maxCount(int m, int n, vector<vector<int>>& ops) {
        int mina = m, minb = n;
        for (const auto& op: ops) {
            mina = min(mina, op[0]);
            minb = min(minb, op[1]);
        }
        return mina * minb;
    }
};

        

          
        
        
        

          

          AI 代码解读