Skip to content

Latest commit

 

History

History

2251.Number-of-Flowers-in-Full-Bloom

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

2251.Number-of-Flowers-in-Full-Bloom

非常明显的差分数组。因为flowers的数值范围非常大,假如某朵花从第1天开到1e9天,我们不可能对于其中每一天都做标记。所以我们只需要在第1天标记“从此多开一朵花”,在第1e9+1天标记“从此少开一朵花”即可。也就是说,我们只需要关注每个开花区间的第一天和最后一天,就掌握整个区间的信息。

据此我们可以将差分数组建立起来:diff[i]表示第i天比之前多开多少花,注意这可以是正数,也可以是负数。然后就是双指针,我们把persons按照时间遍历,相应地diff数组也单调地遍历。如果某人是在第i天来看花,那么我们就将第i天及其之前的差分信息都累加起来,就得到这个人能够看到的花的总数了。