leetcode-598-范围求和II

直线上最多的点数

题面

leetcode题目

给定一个初始元素全部为 $0$，大小为 $m\times n$ 的矩阵 $M$ 以及在 $M$ 上的一系列更新操作。

操作用二维数组表示，其中的每个操作用一个含有两个正整数 $a$ 和 $b$ 的数组表示，含义是将所有符合 $0\le i<a$ 以及 $0\le j<b$ 的元素 $M[i][j]$ 的值都增加 $1$。

在执行给定的一系列操作后，你需要返回矩阵中含有最大整数的元素个数。

数据范围

• $m$ 和 $n$ 的范围是 $[1,40000]$。
• $a$ 的范围是 $[1,m]$，$b$ 的范围是 $[1,n]$。
• 操作数目不超过 $10000$。

题解

总体思路

脑内想象一下把所有操作的范围画在原矩阵上，可以看出所有的操作都是以原点开始的一个个叠加的子矩阵。

由于每一次操作都是固定的行为$+1$，所以最大的整数一定出现在叠加次数最多的部分，也就是$min(a_1,a_2,a_3,\cdots ,a_n)\times min(b_1,b_2,b_3,\cdots ,b_n)$

!!! note 注意 最终结果不能超过原矩阵的大小，此corner case出现在没有任何操作输入的时候。

代码

#include <iostream>
#include <vector>
using namespace std;

#define _DEBUG
#define MAX 40000
int min(int x, int y)
{
    return x < y ? x : y;
}

class Solution
{
public:
    int maxCount(int m, int n, vector<vector<int>> &ops)
    {
        int minm, minn;
        minm = minn = MAX + 1;
        for (auto iter = ops.begin(); iter != ops.end(); iter++)
        {
            int a = (*iter)[0];
            int b = (*iter)[1];
            minm = min(minm, a);
            minn = min(minn, b);
        }

        int count = minm * minn;
        int max = m * n;
        return min(count, max);
    }
};
// for test
int main()
{
    Solution s;
    vector<vector<int>> test1{{2, 2}, {3, 3}};
    cout << s.maxCount(3, 3, test1) << endl;
    vector<vector<int>> test2{};
    cout << s.maxCount(3, 3, test2) << endl;

    return 0;
}