天际线问题

高度只会在楼的边界处变化:有楼进场(左边)可能变高,有楼退场(右边)可能变矮。所以我们只需盯住所有楼的左右端点,在这些 x 处检查当前最高高度。

把每栋楼拆成两个事件:左端=进场、右端=退场。所有事件按 x 排序,从左到右逐个处理。进场就把高度丢进大根堆,堆顶永远是当前最高;退场的楼到期了就清出去。堆顶高度一变,就记一个关键点。

第 0 步 · 拆事件 + 排序：A[1,4) 拆成「x=1 进场」「x=4 退场」;B[3,6) 拆成「x=3 进」「x=6 退」;C[5,8) 拆成「x=5 进」「x=8 退」。6 个事件按 x 排好队:1,3,4,5,6,8。指针从最左开始,一个一个处理。

下面用楼栋图看轮廓怎么长出来,用大根堆看高度怎么维护。盯住三样:扫描线 x(从左推到右)、大根堆堆顶(当前最高)、关键点(堆顶一变就记一笔)。

起点 · 一片空地：正式开扫前,场上一栋楼都没进来,当前最高 = 地面 0。下面这 7 个台阶位代表 x=1~8 的各段轮廓,先全是 0;扫描线从最左往右推,每处理一个事件就可能抬高或压低某段。

事件 x=1 · A 进场 (高 3)：扫描线推到 x=1,A 进场,高度 3 丢进堆。堆里原本只有「地面 0」,现在堆顶变成 3——比之前的 0 高了,高度变化了,记下第一个关键点 [1,3]。轮廓从地面升到 3。

堆维护 · A 入堆,堆顶=3：堆里永远在堆底垫一个「地面 0」(右端当无穷大、永不退场),这样所有楼都退场后堆顶自然是 0,轮廓落地。现在堆顶是 A 的 3。

事件 x=3 · B 进场 (高 4)：扫描线到 x=3,B(高 4)进场入堆。此刻 A、B 都在场,堆顶从 3 升到 4(B 更高)。高度变了,记关键点 [3,4]。注意 x=1~3 这段轮廓仍是 A 的高度 3。

堆维护 · B 入堆①·先挂末尾：入堆分两步。第一步:B 的高度 4 先塞到堆的最末尾。它的父亲是堆顶 3,可 4 比 3 大,违反了「父 ≥ 子」的大根堆规矩,接下来让它往上冒。

堆维护 · B 入堆②·上浮到顶：第二步「上浮」:4 和父亲 3 比,4 更大就交换,一路往上冒到顶。现在堆顶是 B 的 4,3(A)沉下去当孩子。这就是堆维持「堆顶最大」的内部动作。

事件 x=4 · A 退场 (右端到了)：扫描线到 x=4,这是 A 的右端,A 退场。但当前最高是 B 的 4,A 本来就不是堆顶,它走不走不影响堆顶。堆顶还是 4,高度没变,不记关键点。x=3~4 这段轮廓延续 4。

堆维护 · A 该退场,但它在堆里面：大根堆只能从堆顶取走元素,没法直接抠出中间的 A。用「懒删除」:每个高度都记着自己的右端,过期了先不管,等它升到堆顶时(下次取堆顶前)再统一清掉。所以堆里给每个高度都带了「右端」这个标签。

事件 x=5 · C 进场 (高 2)：扫描线到 x=5,C(高 2)进场入堆。但 C 才 2,比当前堆顶 4(B)矮,沉到堆里当孩子,堆顶还是 4。高度没变,不记点。此刻在场的有 B(4)和 C(2),最高仍是 4。

堆维护 · C 入堆,沉底：C 的高度 2 入堆,它远小于堆顶 4,不会浮上来,堆顶纹丝不动。注意此刻堆里还混着已过期的 A(3),但它没在堆顶、暂时不碍事——这正是懒删除「先留着」的样子。

事件 x=6 · B 退场 · 清栈①：扫描线到 x=6,B 的右端到了。取当前最高前先清栈:堆顶 B(右端 6)≤ 6,过期,弹出!之前那段(x=4~6)轮廓维持的 4 到这里结束。把灰掉的旧楼清出去后,看看新堆顶是谁。

堆维护 · 清栈①·弹掉过期堆顶 B：弹掉 B 后,之前一直赖在堆里的过期 A(高 3)这下浮到了堆顶。它的右端 4 也早 ≤ 6——所以清栈不止弹一次,要一直弹到堆顶不再过期为止。这就是懒删除「攒到一起清」的时刻。

堆维护 · 清栈②·再弹过期的 A：再弹掉过期的 A,堆顶变成 C 的 2(右端 8,还没过期,停止清栈)。当前最高从 4 掉到 2,高度变了,记关键点 [6,2]。轮廓在 x=6 从 4 跌到 2。

x=6 后 · 轮廓跌到 2：B 走了,场上只剩 C(高 2)。x=6 起轮廓降到 2。看楼栋图:左边 4 的台阶到 x=6 结束,接上 C 的矮台阶 2。关键点 [6,2] 正是这个下降的拐角。

事件 x=8 · C 退场 · 落地：扫描线到 x=8,C 的右端到了。清栈弹掉堆顶 C(右端 8 ≤ 8),堆里只剩垫底的地面 0。当前最高 4...不,是 0——没楼了,轮廓落回地面。记最后一个关键点 [8,0]。

堆维护 · 取堆顶 C·末尾补位：再看一眼「取堆顶」的内部动作:不是直接抠掉堆顶,而是把末尾元素搬到顶补空,再让它和孩子比、必要时一路下沉归位。这里末尾正好是地面 0,搬上来即合法。

堆维护 · C 出堆,只剩地面 0：幸亏堆底一直垫着「地面 0」:所有楼退场后,堆顶自然是 0,轮廓优雅落地。这就是为什么初始化时往堆里塞一个高度 0、右端无穷大的哨兵——省去判空的麻烦。

全程回放 · 天际线成形：整条天际线就是这串台阶:x=1 升到 3,x=3 升到 4(B 盖过 A),x=6 跌到 2(只剩 C),x=8 落地 0。4 个关键点 [1,3]、[3,4]、[6,2]、[8,0] 标出每个高度变化的拐角,和手算、和代码实跑完全一致。

别被「进场就升、退场就降」骗了。x=4 A 退场但堆顶没变(B 更高)、x=5 C 进场但堆顶没变(C 太矮),都不记点。轮廓只在「当前最高换了高度」时拐弯,这个判断完全交给堆顶。

提速对比：关键提速两点:① 只在端点处理(2n 个),不管中间无变化的坐标;② 用大根堆把「当前最高」从每次 O(n) 重扫降到取堆顶 O(1)、维护 O(log n)。

边界三连：边界都在测「高度没变就别记点」:重叠、同高、首尾相接,只要当前最高没换数值,中间就不该冒出多余的关键点。

面试追问：面试高频三连:同 x 的进退顺序(进场优先)、Python 大根堆的取负技巧、堆里为何要带右端标签。