LeetCode 2848. 与车相交的点（差分法、前缀和）

题目：2848. 与车相交的点

思路：差分+前缀和。先找到数组中的最大值N，然后构建一个长度为N+2的数组sta。接着遍历数组，进行差分。最后求前缀和得到每个点的值，然后判断是否大于0即可。时间复杂度0(n)。

class Solution {
public:
    int numberOfPoints(vector<vector<int>>& nums) {
        int N=0;
        //找到数组中的最大值N
        for(auto x:nums){
            N=max(x[1],N);
        }
        //构建一个长度为N+2的数组sta，进行差分
        vector<int> sta(N+2,0);
        for(auto x:nums){
            sta[x[0]]++;
            sta[x[1]+1]--;
        }
        //求前缀和得到每个点的值s，然后判断是否大于0
        int ans=0,s=0;
        for(int i=0;i<=N+1;i++){
            s+=sta[i];
            if(s>0) ans++; 
        }
        return ans;
    }
};