题目：
难度：Hard
相关话题：堆、树状数组、线段树、分治算法、Line Sweep
城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。现在，假设您获得了城市风光照片（图A）上显示的所有建筑物的位置和高度 ，请编写一个程序以输出由这些建筑物形成的天际线 （图B）。
每个建筑物的几何信息用三元组 [Li，Ri，Hi] 表示，其中 Li 和 Ri 分别是第 i 座建筑物左右边缘的 x 坐标， Hi 是其高度。可以保证 0 ≤ Li, Ri ≤ INT_MAX , 0 < Hi ≤ INT_MAX 和 Ri - Li > 0 。您可以假设所有建筑物都是在绝对平坦且高度为 0 的表面上的完美矩形。
例如，图A中所有建筑物的尺寸记录为： [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] 。
输出是以 [ [x1,y1], [x2, y2], [x3, y3], ... ] 格式的“关键点 ”（图B中的红点）的列表，它们唯一地定义了天际线。关键点是水平线段的左端点 。请注意，最右侧建筑物的最后一个关键点仅用于标记天际线的终点，并始终为零高度。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。
例如，图B中的天际线应该表示为： [ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ] 。
说明:
任何输入列表中的建筑物数量保证在 [0, 10000] 范围内。
输入列表已经按左 x 坐标 Li 进行升序排列。
输出列表必须按 x 位排序。
输出天际线中不得有连续的相同高度的水平线。例如 [...[2 3], [4 5], [7 5], [11 5], [12 7]...] 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个： [...[2 3], [4 5], [12 7], ...]
思路：
重新构建建筑顶点数组，内部格式为[x,y,state]，x代表横坐标，y代表纵坐标，state代表当前是上升还是下降。
按x从小到大排序。
使用优先队列，添加每一个的高度y，并且维护一个变量max，用来保存当前顶点的最高的y。
当state表示上升时，首先添加y到优先队列pq，
如果当前的y>max，说明有一幢房子超过原来最高的，需要添加当前的[x,y]；
如果当前y<=max，说明这幢房子和原来最高的叠加了；
当state表示下降时，首先从pq中删除匹配的y。
如果当前y===max，说明最高的房子就到这个x为止，检查pq中的下一个最大的y，并且更新max，添加结果，如果不存在，则为0。
如果当前y<max，说明这个被最高的房子遮挡住的一幢房子就到此x，不必再做任何事情。
排序时有3个边界情况：
当x相同，并且同为上升状态，y更大的排前面，优先处理它那么y更小的就会被忽略。
当x相同，并且同为下降状态，y更小的排前面。
当x相同，一个上升，一个下降，那么先处理上升状态的房子，因为这种情况就是2幢房子合并在一起，下降的点可以忽略。
/**
* @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
* @param {number[][]} buildings
* @return {number[][]}
*/
var getSkyline = function(buildings) {
let vertexes=[]
for(let i=0;i<buildings.length;i++){
let [s,e,h]=buildings[i]
vertexes.push([s,h,0],[e,h,1])
}
vertexes.sort((a,b)=>{
// 默认按从小到大排序
if(a[0]<b[0])return -1
else if(a[0]>b[0])return 1
else{
// 都是S，从大到小
if(a[2]===0 && b[2]===0)return b[1]-a[1]
// 都是E，从小到大
else if(a[2]===1 && b[2]===1)return a[1]-b[1]
// 一个S一个E，先S后E
else{
if(a[2]===0)return -1
else return 1
}
}
})
let pq=[],max=0
let result=[]
function bsEnd(arr,n){
let lo=0,hi=arr.length-1
while(lo<hi){
let mid=Math.floor((lo+hi)/2)
if(arr[mid]<n)lo=mid+1
else hi=mid
}
return hi
}
function insert(n){
if(pq.length===0 || n>=pq[pq.length-1]){
pq.push(n)
}else{
pq.splice(bsEnd(pq,n),0,n)
}
}
function remove(n){
pq.splice(bsEnd(pq,n),1)
}
function getMax(){
if(pq.length===0)return 0
return pq[pq.length-1]
}
for(let i=0;i<vertexes.length;i++){
let [x,y,state]=vertexes[i]
if(state===0){
insert(y)
if(y>max){
max=y
result.push([x,y])
}
}else{
remove(y)
let curMax=getMax()
if(y===max && curMax!==max){
max=curMax
result.push([x,max])
}
}
}
return result
};
扩展阅读：