前言
每天和你一起刷 LeetCode 每日一题~
LeetCode 启动!
今天的题目曾经的我做过了 . . . 又是复习的一天
题目:与车相交的点
代码与解题思路
func numberOfPoints(nums [][]int) (ans int) { diff := [102]int{}for _, p := range nums {diff[p[0]]++diff[p[1]+1]--}s := 0for _, d := range diff {s += dif s > 0 {ans++}}return ans
}
首先,这道题为什么用差分?
如果对差分不太了解,可以看我之前总结的前缀与差分:前缀与差分算法思想与模版
用一句话来总结差分的思想,那就是:用 O(N) 的复杂度构建差分数组,通过这种方式达成 O(1) 的时间让一个区域内的值同时 + C
差分的核心就在于,用 O(1) 的时间让一个区域内的值同时 +C,而空数组本身就是一个差分数组,我们直接通过构造差分数组的方式(核心的 insert 操作),将题目给出的区间都 +1,统计 > 0 的位置个数即可得出答案
视频实况
【【LeetCode】每日一题 2024_9_15 与车相交的点(差分)】
每天进步一点点
可以和我刷一辈子的每日一题吗?
一题一题,积累起来就是一辈子。