Skip to content

Latest commit

 

History

History

2345.Finding-the-Number-of-Visible-Mountains

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

2345.Finding-the-Number-of-Visible-Mountains

本题的突破点在于这个发现:如果三角形A的左端点早于三角形B的左端点,那么A一定不会被B覆盖。所以将所有的三角形按照左端点排序,那我们能看到的三角形的顺序一定不会违反这个序列。

接下来思考,虽然A不会被B覆盖,但是B依然可能会被A覆盖。如何判定呢?其实就取决于A的右端点是否足够远。如果A的右端点足够远,那么它有可能还会覆盖后续的若干个三角形。

所以基本思想就是,将所有三角形按照左端点排序,遍历每个三角形的时候维护当前最远的右端点的位置far。任何新的三角形的右端点的位置如果在far前面,就说明它是会被前面的三角形所覆盖的。

本题的corner case是,如果有两个三角形的左端点相同,那如何排序?不难想到,我们先处理右端点更远的,这样就保证它能把其他的三角形给遮盖了。