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 } }