Building Outline

这属于sweep line问题,一开始我想到把所有边放到堆里排序这没问题。但在取出来的时候没有用合适的数据结构,造成了判断end point的情况特别复杂。如果自己觉得情况很复杂的时候,多半是方向错了。从左到右扫描的时候用的是max heap来帮助找到高度变化的点,因为当前建筑的高度是最高点决定的,自动过滤到新进来的比最高点小的起点。遇到end就删除相应的start。

高度变化有2种情况:
1.升高,新的start比现有最高点高。把新的高度加入heap.
2.下降,现在这个高度达到end,heap里面高度为空。

lintcode需要求start,end,height,增加了程序的复杂度。end有两种情况:
1.start变了也就是cur height!= heap top.
2.end后面就是陆地高度为零。这个时候heap里面没有存任何高度。 heap.peek()==0


实现方面,可以用一个int[2]代替Point 类。把start point的高度设置为负。虽然代码量减少了,但是可读性也下降了。不建议这样做,还是老老实实写Point 类。


 from left to right  
 {  
      if(start edege)  
           add height to heap  
      else  
           remove height from heap  

     //pre!=null 要排除pre前面是陆地的情况
      if(heap top ==0 or cur height != heap top)  
      {  
           if(pre!=null && pre height != cur height)  
                add range(pre to cur) to result  
           if(top==0)  
           {  
                pre= null  
           }  
           else  
                pre=cur  
      }  
 }       

评论

此博客中的热门博文

776. Split BST

663. Equal Tree Partition

532. K-diff Pairs in an Array