【数据结构-一维差分】力扣2848. 与车相交的点
给你一个下标从 0 开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i，nums[i] = [starti, endi] ，其中 starti 是第 i 辆车的起点，endi 是第 i 辆车的终点。
返回数轴上被车 任意部分 覆盖的整数点的数目。
示例 1：
输入：nums = [[3,6],[1,5],[4,7]]
输出：7
解释：从 1 到 7 的所有点都至少与一辆车相交，因此答案为 7 。
示例 2：
输入：nums = [[1,3],[5,8]]
输出：7
解释：1、2、3、5、6、7、8 共计 7 个点满足至少与一辆车相交，因此答案为 7 。
差分
class Solution {
public:
int numberOfPoints(vector<vector<int>>& nums) {
auto it = std::max_element(nums.begin(), nums.end(), [](const auto& a, const auto& b) {
return a[1] < b[1];
});
int max_end = (*it)[1];
vector<int> dif(max_end+2);
for(auto& i : nums){
dif[i[0]]++;
dif[i[1]+1]--;
}
int ans = 0, s = 0;
for(int d : dif){
s += d;
ans += s > 0;
}
return ans;
}
};
传统的暴力方法时间复杂度接近N^2，而差分方法时间复杂度在N。
差分的基础知识https://leetcode.cn/problems/points-that-intersect-with-cars/solutions/2435384/chai-fen-shu-zu-xian-xing-zuo-fa-by-endl-3xpm/