Skip to content

Commit 9ba34b3

Browse files
authored
Update Readme.md
1 parent 7a22ee7 commit 9ba34b3

1 file changed

Lines changed: 1 addition & 1 deletion

File tree

  • Others/2015.Average-Height-of-Buildings-in-Each-Segment

Others/2015.Average-Height-of-Buildings-in-Each-Segment/Readme.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22

33
对于给出若干个区间、涉及到区间合并的问题,扫描线是比较自然的想法。
44

5-
我们只关注那些建筑两边的边缘线位置。将所有的边缘线按照位置从小到大排序之后,我们逐个遍历一遍。维护一个集合,遇到左边缘就插入h,遇到右边缘就删除h。于是,我们在每一个边缘线位置pos,都可以通过这个集合得到一个平均值avg,这意味着从pos往右直至下一个边缘线位置pos2,中间这部分区间[pos, pos2]就是一个输出为avg的线段
5+
我们只关注那些建筑两边的边缘线位置。将所有的边缘线按照位置从小到大排序之后,我们逐个遍历一遍。维护一个集合,遇到左边缘就插入h,遇到右边缘就删除h。于是,我们在每一个边缘线位置pos,都可以通过当前集合得到一个平均值avg,这意味着从pos往右直至下一个边缘线位置pos2,中间这部分区间[pos, pos2]就是一个输出恒为avg的线段
66

77
我们将这些琐碎的线段收集起来,合并输出相同的线段,并且剔除输出为0的线段,这剩余的这些线段就是答案。
88

0 commit comments

Comments
 (0)