天际线问题如何用分治合并轮廓？和扫描线有什么区别？

简化版

天际线问题可以用分治：先把建筑列表分成两半，分别求左右天际线，再合并两条轮廓。

合并时用两个指针扫描关键点，维护左右当前高度，当前位置的真实高度是 max(leftHeight, rightHeight)。

如果高度变化，就加入一个新的关键点；高度不变则跳过，避免冗余。

详细版

每栋建筑 [left, right, height] 可以看成一条简单轮廓：[left, height] 和 [right, 0]。

分治时：

单栋建筑直接返回它的轮廓；
多栋建筑分成左右两组；
递归求出左右天际线；
像合并两个有序数组一样合并关键点。

合并的关键是：同一个 x 坐标处，天际线高度取左右轮廓当前高度的最大值。

分治复杂度通常是 O(n log n) 级别，扫描线 + 堆也是常见解法。

完整版教学

一、天际线本质是什么

天际线是建筑外轮廓的上边界。结果不是每个坐标的高度，而是一组关键点：只有高度发生变化的位置才需要记录。比如从高度 3 持续到高度 3，中间不需要重复点；当高度从 3 变成 5，才产生新的关键点。

记忆钩子：天际线只记录“高度变化点”，不是记录每一栋楼。

二、为什么可以分治

如果把建筑分成左右两组，分别求出它们各自的天际线，那么总天际线就是两条轮廓叠加后的上包络。上包络在每个 x 坐标处取两边当前高度的最大值。这个合并过程和归并排序合并两个有序数组很像，只是比较对象从数值变成了 x 坐标和高度。

子问题	输出	合并方式
左半建筑	左天际线关键点	双指针扫描
右半建筑	右天际线关键点	双指针扫描
总建筑	上包络关键点	取当前最大高度

分治能成立，是因为轮廓可以独立求解再合并。

三、单栋建筑如何表示

一栋建筑 [l, r, h] 的轮廓是：

[l, h], [r, 0]

在 l 处高度升到 h，在 r 处高度降回 0。多个建筑的天际线就是这些轮廓叠加后的结果。

四、合并两条天际线

合并时维护两个当前高度 h1 和 h2。每次取较小的 x 坐标向前推进，并更新对应轮廓的高度。当前位置真实高度是：

height = max(h1, h2)

如果这个高度和结果中最后一个高度不同，就加入关键点。

function addPoint(ans, x, h) {
  if (ans.length === 0 || ans[ans.length - 1][1] !== h) {
    ans.push([x, h])
  }
}

这一步能去掉连续相同高度的冗余点。

五、代码骨架

核心结构如下：

function getSkyline(buildings) {
  function solve(l, r) {
    if (l === r) {
      const [x1, x2, h] = buildings[l]
      return [[x1, h], [x2, 0]]
    }
    const mid = Math.floor((l + r) / 2)
    return mergeSkyline(solve(l, mid), solve(mid + 1, r))
  }
  if (buildings.length === 0) return []
  return solve(0, buildings.length - 1)
}

完整实现重点在 mergeSkyline，它本质是两个有序关键点列表的合并。

六、常见误区与追问

误区：把每栋楼的左右端点直接输出。 重叠建筑会遮挡低楼，必须取上包络。
误区：合并时不去重相同高度。 结果会出现冗余关键点，不符合题目输出要求。
误区：只按建筑排序，不处理轮廓叠加。 天际线高度来自所有覆盖当前 x 的建筑最大高度。
追问：扫描线和分治怎么选？ 扫描线用事件和堆维护活动建筑；分治用轮廓合并，两者复杂度都较好。
追问：同一个 x 有多个关键点怎么办？ 要合并处理，最终只保留该 x 下真实高度变化后的结果。

这些点考的是区间重叠和轮廓合并。

七、加强记忆

天际线分治记成“单楼两点，左右轮廓，上包络合并”。每个子问题输出关键点列表，合并时两个指针按 x 推进，当前高度取左右高度最大值。只有高度变化时才加入答案。它和扫描线都在维护“当前最高建筑”，只是组织方式不同。

简化版

详细版