2848. 与车相交的点

Leetcode题目:差分数组

给你一个下标从 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 。

提示:

  • 1 <= nums.length <= 100
  • nums[i].length == 2
  • 1 <= starti <= endi <= 100

解题思路

差分数组

我是不知道为啥要划分到前缀和分类的,最后毕竟是对整个diff数组求和,但又感觉维护diff数组的时候又有那么点前缀和的思想在里头。

class Solution {
public:
    int numberOfPoints(vector<vector<int>>& nums) {
        int diff[102]{0};
        int result=0;
        for(auto &i:nums)
        {
            diff[i[0]]++;
            diff[i[1]+1]--;
        }
        int sum=0;
        for(int &i:diff)
        {
            sum+=i;
            if(sum>0)
            {
                result++;
            }
        }
        return result;
    }
};
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
在此留下你的评论x