天际线

题意

给出若干建筑 (left, height, right)，按横坐标顺序输出城市轮廓每次高度改变的位置和新高度。

思路

在每个左端点把 (-height, right) 放入堆，并为每个右端点建立事件。扫描到横坐标 x 时，先加入同坐标的新建筑，再弹出所有 right <= x 的过期建筑。堆顶就是当前位置最高的有效建筑。

只有堆顶高度发生变化时才输出折点。同坐标事件必须整体处理，否则会输出不存在的中间轮廓。

Python 知识

heapq 只有最小堆，用负高度模拟最大堆。
zip(data, data, data) 可把同一个整数迭代器每三个元素分成一组建筑数据。
answer += [x, height] 直接构造题目要求的一维输出序列。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37import sys
from collections import defaultdict
from heapq import heappop, heappush


starts = defaultdict(list)
positions = set()
data = list(map(int, sys.stdin.buffer.read().split()))

# 按所有空白读取，再把每三个整数作为一幢建筑。
for i in range(0, len(data), 3):
    left, height, right = data[i], data[i + 1], data[i + 2]
    # heapq 是最小堆，保存负高度后，堆顶就是最高建筑。
    starts[left].append((-height, right))
    # 天际线只可能在建筑的左右端点发生变化。
    positions.update((left, right))

heap = []
answer = []
last_height = 0

for x in sorted(positions):
    # 扫描到左端点时，将这里开始的所有建筑加入堆。
    for building in starts[x]:
        heappush(heap, building)

    # 惰性删除已经在当前位置结束的建筑。
    while heap and heap[0][1] <= x:
        heappop(heap)

    height = -heap[0][0] if heap else 0
    # 最高高度改变时，当前位置才是轮廓折点。
    if height != last_height:
        answer.extend((x, height))
        last_height = height

print(*answer)

复杂度

时间复杂度 $O(n\log n)$ ，空间复杂度 $O(n)$ 。

总结

天际线的关键是“事件排序 + 惰性删除过期建筑 + 只记录最高高度变化”。

目录

题意

思路

Python 知识

代码

复杂度

总结