Open caibirdme opened 4 years ago
The Skyline Problem 这道题就是线段扫描一个很典型的题目, 目的就是从左到右扫描各条线段. 但是由于线段跨度可能很大, 而我们关注的是左右边界, 所以常见的办法就是把线段拆成左右两个点, 分别记录坐标和值, 并且可以利用值的正负来表达线段的起点和终点(PS: 如果线段值本来就可能为负,就需要额外的标记了.) 把线段拆成两个点之后, 我们就需要进行双关键字排序. 先按x轴从小到大,然后根据题意排序另一个关键字. 此题为了避免[1,3,h], [3,5,h] -> (1,h) (-3,h) (3,h) (-5,h)这种情况出现, 我们把高度为正的排到前面.
[1,3,h], [3,5,h] -> (1,h) (-3,h) (3,h) (-5,h)
排序完之后开始扫描. 由于天际线关注的是当前扫描到的线段的最大高度值, 因此我们需要有个数据结构维护我们扫描到的线段的高度值,可以方便的插入删除并且取最大. heap不太合适, 因为heap只能插入取最值以及删除最值, 除非实现一个intrisive的heap, 但是太麻烦. 最好的选择就是用orderedMap. 每次来一个正值, 代表一个线段的左端点出现, 我们插入这个值, 如果是负值, 我们就把对应高度(-h)减一, 如果为0则删除该高度. 然后每次去检查orderedMap的最大值是否发生变化. 变化的地方就是我们的skyline的变化点
The Skyline Problem 这道题就是线段扫描一个很典型的题目, 目的就是从左到右扫描各条线段. 但是由于线段跨度可能很大, 而我们关注的是左右边界, 所以常见的办法就是把线段拆成左右两个点, 分别记录坐标和值, 并且可以利用值的正负来表达线段的起点和终点(PS: 如果线段值本来就可能为负,就需要额外的标记了.) 把线段拆成两个点之后, 我们就需要进行双关键字排序. 先按x轴从小到大,然后根据题意排序另一个关键字. 此题为了避免
[1,3,h], [3,5,h] -> (1,h) (-3,h) (3,h) (-5,h)这种情况出现, 我们把高度为正的排到前面.排序完之后开始扫描. 由于天际线关注的是当前扫描到的线段的最大高度值, 因此我们需要有个数据结构维护我们扫描到的线段的高度值,可以方便的插入删除并且取最大. heap不太合适, 因为heap只能插入取最值以及删除最值, 除非实现一个intrisive的heap, 但是太麻烦. 最好的选择就是用orderedMap. 每次来一个正值, 代表一个线段的左端点出现, 我们插入这个值, 如果是负值, 我们就把对应高度(-h)减一, 如果为0则删除该高度. 然后每次去检查orderedMap的最大值是否发生变化. 变化的地方就是我们的skyline的变化点