“城市天际线（The Skyline Problem）”是计算机科学中极其经典的一道算法题（LeetCode 218题，难度：Hard），也是扫描线算法（Sweep Line） 最纯粹、最惊艳的应用场景。
它完美展示了如何将“静态的二维几何重叠问题”，通过扫描线降维成“一维的动态状态流转问题”。
一、 问题详细描述
假设你是一名城市规划师，站在城市的正前方（二维平面的侧面）观察一排建筑物。你需要画出这些建筑物在天空背景下形成的外轮廓线（天际线）。
输入：一个列表 buildings，其中每个元素是一个三元组 [left, right, height]：
-
left：建筑物左边缘的 X 坐标。
-
right：建筑物右边缘的 X 坐标。
-
height：建筑物的高度。
-
假设所有建筑物都建在高度为 0 的绝对平坦的地面上，且都是完美的矩形。
输出：一个列表 skyline，包含一系列坐标点 [x, y]。
-
[x, y] 表示天际线在水平位置 x 处，高度发生了改变，新的高度为 y。
-
输出的最后一个点必须是天际线的终点，高度永远为 0。
-
核心约束（去重与合并）：输出中不能包含连续的、相同高度的水平线段。只有当高度发生“转折（变化）”时，才记录一个点。
二、 测试数据
我们构造 5 栋建筑物，包含了重叠、包含、相邻、间隙、高度跌落等所有复杂边缘场景。
buildings = [
[2, 9, 10], # B1: 较宽，中等高度
[3, 7, 15], # B2: 较窄，很高，被 B1 和 B3 夹在中间
[5, 12, 12], # B3: 较宽，中等高度，与 B1、B2 都有重叠
[15, 20, 10], # B4: 独立建筑，与前面有间隙 (Gap)
[19, 24, 8] # B5: 与 B4 尾部重叠，但比 B4 矮
]
扫描线推演（X轴从左向右扫）：
-
X=2: 碰到 B1 左边缘，高度从 0 升到 10。 (记录点 [2, 10])
-
X=3: 碰到 B2 左边缘，高度从 10 升到 15。 (记录点 [3, 15])
-
X=5: 碰到 B3 左边缘，但 B3 高度(12) < 当前最大高度(15)，被遮挡，不记录。
-
X=7: 碰到 B2 右边缘（高楼离开），高度从 15 跌落。此时扫描线上还有 B1(10) 和 B3(12)，最高的是 B3，所以高度跌落到 12。 (记录点 [7, 12])
-
X=9: B1 离开，但 B3(12) 还在，最高仍是 12，无变化，不记录。
-
X=12: B3 离开，扫描线上无建筑，高度跌落到 0。 (记录点 [12, 0])
-
X=15: 碰到 B4，高度从 0 升到 10。 (记录点 [15, 10])
-
X=19: 碰到 B5，但 B5(8) < B4(10)，被遮挡，不记录。
-
X=20: B4 离开，高度跌落到 B5 的高度 8。 (记录点 [20, 8])
-
X=24: B5 离开，高度跌落到 0。 (记录点 [24, 0])
正确输出：[[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]
三、 核心解法：扫描线 + 最大堆
在天际线问题中，我们需要知道的是当前扫描线上所有活跃建筑的 “最大高度”。
因此，我们需要将 SUM() 替换为一个能动态维护最大值的数据结构：
-
在 C++ 中是 std::multiset。
-
在 Python 中是 heapq（优先队列/最大堆）。
-
在 Java 中是 TreeMap 或 PriorityQueue。
算法执行步骤（标准 4 步法变体）：
事件拆解：将每个建筑 [L, R, H] 拆为两个事件：[L, -H] (进入，用负数表示左边缘以便排序) 和 [R, H] (离开，用正数表示右边缘)。
事件排序：按 X 坐标升序排列。
（核心避坑点：如果 X 相同，必须先处理左边缘，且左边缘中较高的先处理；右边缘中较矮的先处理。使用负数高度可以完美利用默认升序排序解决此冲突！）
状态扫描（最大堆）：维护一个包含当前所有“活跃建筑高度”的最大堆。遇到左边缘，高度入堆；遇到右边缘，高度出堆。
转折提取：每次堆顶元素（当前最大高度）发生变化时，记录 [X, 新最大高度]。
四、 高级 SQL 实现 (降维打击)
如果在数据仓库（如 Hive, Spark SQL, PostgreSQL）中，我们需要对城市里几百万栋建筑计算天际线，写 Python UDF 太慢。我们可以完全利用 SQL 的窗口函数和扫描线思想来解决！
SQL 解题思路：
行转列：把建筑拆成 x 和 h 的事件点。
网格化（离散化）：因为 SQL 没有“堆”这种内存数据结构，我们需要找出所有发生高度变化的关键 X 坐标（即所有建筑的左右边缘）。
区间覆盖判断：对于每一个关键 X 坐标，找出所有跨越这个 X 坐标的建筑，取它们的 MAX(height)。
去重合并：利用 LAG() 剔除连续相同的高度。
WITH
— 原始数据
buildings AS (
SELECT * FROM (VALUES
(1, 2, 9, 10),
(2, 3, 7, 15),
(3, 5, 12, 12),
(4, 15, 20, 10),
(5, 19, 24, 8)
) AS t(id, left_x, right_x, height)
),
— 步骤 1：提取所有关键的 X 坐标（扫描线会停留的所有“事件点”）
critical_x AS (
SELECT left_x AS x FROM buildings
UNION
SELECT right_x AS x FROM buildings
),
— 步骤 2：对于每一个关键 X 坐标，找出覆盖它的所有建筑，并求出最大高度
— 注意：建筑覆盖的条件是 left_x <= x AND x < right_x (左闭右开区间，避免右边缘被重复计算)
x_max_height AS (
SELECT
c.x,
COALESCE(MAX(b.height), 0) AS max_h
FROM critical_x c
LEFT JOIN buildings b
ON b.left_x <= c.x AND c.x < b.right_x
GROUP BY c.x
),
— 步骤 3：利用 LAG() 获取上一个 X 坐标的高度，用于判断是否发生“转折”
height_changes AS (
SELECT
x,
max_h,
LAG(max_h) OVER (ORDER BY x) AS prev_max_h
FROM x_max_height
)
— 步骤 4：过滤出高度发生变化的转折点（即天际线输出）
SELECT
x,
max_h AS y
FROM height_changes
WHERE prev_max_h IS NULL — 第一个点
OR max_h != prev_max_h — 高度发生变化的点
ORDER BY x;
SQL 中间过程:
| 2 |
B1(10) |
10 |
NULL |
✅ [2, 10] |
| 3 |
B1(10), B2(15) |
15 |
10 |
✅ [3, 15] |
| 5 |
B1(10), B2(15), B3(12) |
15 |
15 |
❌ (无变化) |
| 7 |
B1(10), B3(12) |
12 |
15 |
✅ [7, 12] |
| 9 |
B3(12) |
12 |
12 |
❌ (无变化) |
| 12 |
无 |
0 |
12 |
✅ [12, 0] |
| 15 |
B4(10) |
10 |
0 |
✅ [15, 10] |
| 19 |
B4(10), B5(8) |
10 |
10 |
❌ (无变化) |
| 20 |
B5(8) |
8 |
10 |
✅ [20, 8] |
| 24 |
无 |
0 |
8 |
✅ [24, 0] |
(SQL 解法虽然时间复杂度是O(N^2) ，但在 MPP 数据库（如 ClickHouse, Spark）中，利用分布式 JOIN 和聚合，处理百万级区间的天际线计算依然非常高效，且代码极具可读性。)
五、 总结：天际线问题带来的思维升华
无论是用 Python 的最大堆，还是用 SQL 的左连接+分组聚合，城市天际线问题都向我们展示了扫描线算法的终极奥义：
打破实体的边界：不要盯着“一栋栋楼”看，要把楼拆碎，变成时间/空间轴上的“事件”。
维护“活跃状态池”：扫描线本身没有记忆，你必须用一个数据结构（堆、Multiset、或者 SQL 的 JOIN 匹配）来记录“当前扫描线穿透了哪些实体”。
只关注“状态突变”：海量的事件点中，90% 都是无效的（被遮挡的、高度没变的）。真正的业务价值（天际线的转折、系统的报警、用户的流失）只发生在状态池的极值（MAX）发生翻转的那一瞬间。
往期精彩
某制造业面试题：LOT历史日志设备空值数据补全问题
面试问：建模中粒度设计不当会造成什么影响？
SQL数据分析实战：电商新品高流量低转化问题
SQL数据分析：购物篮分析
游戏数仓 : 用户行为属性大表整合【宽表设计】
SQL数据分析实战：物流轨迹行为区间划分
SQL数据分析实战：用户WiFi行为区间划分
数据治理：数据波动如何校验？
SQL库存库龄分析实战：库存周期重算问题
在团队中，如何推动一项新技术落地 ？
