leetcode-598-范围求和II

直线上最多的点数

题面

leetcode题目

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

操作用二维数组表示，其中的每个操作用一个含有两个正整数 \(a\) 和 \(b\) 的数组表示，含义是将所有符合 \(0 \leq i < a\) 以及 \(0 \leq 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;
}