城市天际线：同坐标事件合并与高度最大堆

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• building=(left,right,height)，left<right、height>0，覆盖半开[left,right)。
• 返回(x,newHeight)关键点，不输出连续相同高度；空输入空结果。

解题路线

1. 每左端加入(-height,right)，每右端至少产生一个检查事件。按x分组，先加入本时刻新建筑，再从堆顶删除right≤x的到期建筑。
2. 堆顶最高未过期建筑给当前height，若不同于上一段才输出关键点。深处过期项可保留直到成为顶再清，不影响当前最大。
3. 同x结束与开始统一处理后才输出一次，避免同坐标短暂0或多条无面积变化点。floor高度0哨兵永不过期。

手动走一遍

[(1,3,2),(2,4,5)]输出(1,2),(2,5),(4,0)，第一个在3结束不改变最高5。[(1,2,3),(2,4,3)]输出(1,3),(4,0)，接触同高不出现2处伪关键点。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from heapq import heappush,heappop
from itertools import groupby


def skyline(buildings):
    events=[]
    for left,right,height in buildings:
        if left>=right or height<=0:raise ValueError("valid positive buildings required")
        events.append((left,-height,right));events.append((right,0,0))
    heap=[(0,float('inf'))];result=[];last=0
    for x,group in groupby(sorted(events),key=lambda e:e[0]):
        for _,negative,right in group:
            if negative:heappush(heap,(negative,right))
        while heap[0][1]<=x:heappop(heap)
        height=-heap[0][0]
        if height!=last:result.append((x,height));last=height
    return result

复杂度

n建筑，O(nlogn)时间、O(n)堆/事件/输出空间；每建筑至多入堆/清顶一次，lazy项仍占内存直到清理。

易错点与追问

容易失分的边界

• 每个事件单独输出会产生同x重复或不必要高度变化。
• minheap按正height会取最低，需负高度或真正maxheap。

继续深挖

• 输出天际线面积时怎样按相邻关键点积分？
• 实时删建筑时按ID取消、lazyheap及版本如何维护？