LeetCode 218 The Skyline Problem 天际线问题Go 三种解法树状数组 / 线段树 / 扫描线详解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读LeetCode-Go仓库中的 218. The Skyline Problem 题解完整覆盖了「天际线问题」这一经典区间合并题的三种主流解法树状数组、线段树和扫描线。本文以该文档为核心结合仓库内 218. The Skyline Problem.go 的真实实现与 SegmentTree.go、BIT.go 两个通用模板逐行讲解每种解法的核心思想、代码结构与易错细节。读完本文你将掌握「区间最大值无法删除时如何用数据结构迂回维护」「离散化时右边界为什么要减一」「扫描线如何借助索引最大堆完成动态插入与按 key 删除」等关键技巧并能直接复用到 699、715、732 等同类问题。一、题目回顾什么是天际线城市的天际线是从远处观看该城市中所有建筑物所形成的轮廓的外部边界。题目给出所有建筑物的位置与高度图 A要求输出由这些建筑物共同形成的天际线图 B。每个建筑物的几何信息用三元组[Li, Ri, Hi]表示Li、Ri分别是第 i 座建筑物左、右边缘的 x 坐标Hi是其高度约束条件0 ≤ Li, Ri ≤ INT_MAX0 Hi ≤ INT_MAXRi - Li 0所有建筑物都假设是建立在绝对平坦、高度为 0 的地面上的完美矩形。例如图 A 中所有建筑物的尺寸记录为[[2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8]]输出是以[[x1,y1], [x2,y2], [x3,y3], ...]格式表示的「关键点」列表它们唯一地定义了整条天际线。关键点是水平线段的左端点。注意最右侧建筑物结束处的最后一个关键点仅用于标记天际线的终点高度恒为 0任何两座相邻建筑物之间的地面也应被视为天际线轮廓的一部分。例如图 B 中示例的天际线应表示为[[2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24 0]]题目附带的重要约束任何输入列表中的建筑物数量保证在[0, 10000]范围内输入列表已按左 x 坐标Li升序排列输出列表必须按 x 坐标排序输出天际线中不得有连续的同高度水平线。例如[...[2 3], [4 5], [7 5], [11 5], [12 7]...]是不正确的答案三条高度为 5 的线段应在最终输出中合并为一条[...[2 3], [4 5], [12 7], ...]。上述要求直接影响了三种解法的实现细节输出必须去重合并同高度相邻点这也是代码中反复出现res[len(res)-1][1] ! currHeight这类判断的原因。二、题目本质区间最大值维护 转折点维护把问题抽象后可以拆成两个子问题这是整个解题思路的核心脉络原文档 0218.The-Skyline-Problem.md 的 Solution Ideas 一节即围绕这两点展开如何维护区间内的最大值。当一栋高楼的右边界消失后在剩余较矮的楼中仍然要选出最大值作为天际线。可能有大量相互重叠的矮楼残留因此「如何用数据结构维护区间最大值」是这类问题的关键。如何维护天际线的转折点。部分重叠的大楼会产生天际线转折点如上图中的红色转折点数据结构需要能够表达这些点。2.1 树状数组的困境最大值“好加难删”树状数组只有Add()和Query()两个操作。原文档指出Add()可以改为在区间内维护max()但max()容易得到却难以“删除”。例如区间[3,7]的最大值是 15按树状数组的定义区间[3,12]的最大值仍是 15。但从图上可以看到区间[5,12]的实际最大值是 12。当 15 这个高度的楼在 x7 处结束时它不应该继续影响右侧区间——这就是“删除最大值”的难点。解决办法让最大值“晚到”。把Query()的语义从「前缀」改成「后缀」。原本Query(i)查询的是区间[1, i]现在让查询区间变为[i, ∞)。例如区间[i, j]的最大值为max_{i...j}而Query(j1)的查询区间是j1, ∞)自然不包含max_{i...j}从而有效避免了前方高楼对后续区间累计最大值的影响。具体做法把所有区间按 x 值升序排序从左到右遍历区间Add()的含义是把每个区间右边界所代表的后缀区间的最大值累加进去。这样就不需要再考虑“删除”最大值的问题。细心读者可能会问能不能从右往左遍历区间并保持Query()的前缀语义原文档明确回答可行能解决第一个问题维护最大值但在解决第二个问题维护转折点时会遇到麻烦——如果Query()保持前缀语义那么在单点 i 处除了要考虑在该点结束的区间还要额外考虑从单点 i 开始的区间而采用后缀语义时不存在这个问题因为[i1, ∞)区间内不需要考虑在单点 i 结束的区间。2.2 解题思路总览可以用树状数组解Solution 1可以用线段树解Solution 2无需关心“楼挡楼”线段树时间开销偏高可以改用扫描线Solution 3配合最大堆或二叉搜索树动态维护高度。三、解法一树状数组后缀语义 最大值维护对应代码见 [218. The Skyline Problem.go 中的getSkyline。整体思路为每栋楼生成两个Point左边界LEFTSIDE 1和右边界RIGHTSIDE 2记录 x 坐标与楼编号index对所有点按 x 升序排序x 相同时左边界在前side小者在前用kth映射记录每个点排序后的位置这是树状数组的下标遍历所有点遇到左边界时把该楼高度通过bit.Add写入其右边界点对应的位置这就是“把最大值加到后缀区间”随后bit.Query(kth[pt]1)查询当前点之后区间的最大值得到当前位置的天际线高度若当前高度与结果数组中上一个点的高度不同则记录新点若 x 相同则直接覆盖高度值完成同 x 合并。3.1 关键实现区间 max 版的树状数组解法一在题目文件中自定义了一个BinaryIndexedTree类型与仓库 template/BIT.go 中的求和版 BIT 不同后者的Add是tree[index] val、Query是前缀求和。本题专用的版本把换成了max// Add 定义向 index 方向传播最大值 func (bit *BinaryIndexedTree) Add(index int, val int) { for ; index 0; index - index -index { bit.tree[index] max(bit.tree[index], val) } } // Query 定义后缀查询从 index 向 capacity 方向累计最大值 func (bit *BinaryIndexedTree) Query(index int) int { sum : 0 for ; index bit.capacity; index index -index { sum max(sum, bit.tree[index]) } return sum }注意两点Add的循环方向是index - index -index自顶向下传播Query的循环方向是index index -index自底向上累计——正好与求和版 BIT 相反这就是“前缀语义”改为“后缀语义”的具体体现由于 max 操作天然满足结合律Query的累计结果即后缀区间[index, ∞)的最大值。仓库 template/BIT.go 中还提供了InitWithNums的 O(n) 建树优化可作为理解 BIT 底层lowbit结构的参考。四、解法二线段树 离散化右边界减一的关键细节对应代码见 218. The Skyline Problem.go 中的getSkyline1。使用线段树可以完全不用关心“楼挡住楼”的情况。4.1 离散化为什么右边界必须减一由于楼的坐标是离散的先把每栋楼在 X 轴上的两个坐标离散化。原文档特别强调楼的宽度是一个区间但离散化过程中楼的宽度右边界需要减一。原因分析若不减一查询一个区间会包含两个点导致错误。例如第一栋楼是[1,3)楼高 10第二栋楼是[3,6)楼高 20。如果第一栋楼算上右边界 3查询[1,3]的结果是 20——因为[3,3]这个点会查询到第二栋楼上。因此每个楼的右边界应该减一。但每个楼的右边界也必须加入到 query 中因为最终的查询结果需要包含这些边界。在代码的离散化函数discretization218中这一逻辑表现为同时记录三个点tmpMap[pos[0]] // 左边界 tmpMap[pos[1]-1] // 右边界减一用于区间更新 tmpMap[pos[1]] // 右边界用于最终查询4.2 区间更新 单点查询将离散化数据排序后按照楼的信息对每个区间依次 update然后依次统计每个区间的高度如果当前区间高度与前一个区间高度一样视为等高楼不产生新点当高度与前一个高度不同时视为天际线边缘添加到最后输出数组中。核心代码取自 218. The Skyline Problem.gofunc getSkyline1(buildings [][]int) [][]int { st, ans, lastHeight, check : template.SegmentTree{}, [][]int{}, 0, false posMap, pos : discretization218(buildings) tmp : make([]int, len(posMap)) st.Init(tmp, func(i, j int) int { return max(i, j) }) for _, b : range buildings { st.UpdateLazy(posMap[b[0]], posMap[b[1]-1], b[2]) } for i : 0; i len(pos); i { h : st.QueryLazy(posMap[pos[i]], posMap[pos[i]]) if check false h ! 0 { ans append(ans, []int{pos[i], h}) check true } else if i 0 h ! lastHeight { ans append(ans, []int{pos[i], h}) } lastHeight h } return ans }4.3 模板 SegmentTree 的实现要点getSkyline1直接复用仓库通用模板 template/SegmentTree.gost.Init(nums, merge)以max作为合并函数初始化线段树见 SegmentTree.gost.UpdateLazy(updateLeft, updateRight, val)区间更新配合懒标记 lazy 在 O(log n) 内完成由于本题 merge 是幂等的max整段只需套用一次即可 O(1) 下推模板注释中明确对比了「max/min 幂等」与「区间求和 区间加」两种语义的下推差异见 SegmentTree.gost.QueryLazy(left, right)区间查询同样支持懒标记下推见 SegmentTree.go。这里「区间更新定值不是增减」的语义与第 715 题Range Module一致都是将区间内每个点与 val 取 max属于幂等更新。五、解法三扫描线 索引最大堆线段树解法时间开销偏高因此原文档推荐扫描线。对应代码见 218. The Skyline Problem.go 中的getSkyline2。5.1 扫描线思想用一根根垂直于 X 轴的竖线从最左边依次扫到最右边扫描每一条大楼的边界进入大楼左边界时如果当前没有比该左边界最高点更高的点就记录这个最高点为 keyPoint状态为进入如果扫到的大楼左边界存在更高的高度则不记录——因为它不是天际线被其他楼挡在了后面扫到大楼右边界时如果它是当前最高点记录下它的状态为离开同时记录第二高的点。在扫描过程中动态维护大楼的高度。实际上只需要维护最高高度当离开状态到来时移除当前最高的剩余高度中最高的自然就是第二高的高度。文档给出的扫描线伪代码如下// 扫描线伪代码 events {{x: L , height: H , type: entering}, {x: R , height: H , type: leaving}} event.SortByX() ds new DS() for e in events: if entering(e): if e.height ds.max(): ans [e.height] ds.add(e.height) if leaving(e): ds.remove(e.height) if e.height ds.max(): ans [ds.max()]5.2 数据结构选型最大堆 vs 二叉搜索树动态插入、查找最大值可用的数据结构有最大堆和二叉搜索树各有取舍数据结构查找最大值插入按 key 删除最大堆O(1)O(log n)O(n)需自行实现二叉搜索树O(log n)O(log n)O(log n)由于扫描线在离开事件中需要按楼编号删除指定高度的元素而非只删堆顶普通堆的remove_by_key是 O(n) 且需手写因此解法三实现了一个带反向索引的IndexMaxPQ索引最大堆。5.3 IndexMaxPQ支持按 key 删除的最大堆代码位于 218. The Skyline Problem.go结构如下type IndexMaxPQ struct { items []int // key - value高度 pq []int // 二叉堆存 key qp []int // key - 在 pq 中的位置反向索引 total int }Enque(key, val)插入并把新元素swim上浮Front()返回items[pq[1]]即当前最大高度堆空时返回 0对应“地面高度”Remove(key)借助qp反查该 key 在堆中的位置与堆尾交换后sink下沉O(log n) 完成按 key 删除。扫描主循环取自 218. The Skyline Problem.gofor _, e : range es { curH : pq.Front() if e.T 0 { // 进入 if e.H curH { skyline append(skyline, []int{e.X, e.H}) } pq.Enque(e.N, e.H) } else { // 离开 pq.Remove(e.N) h : pq.Front() if curH h { skyline append(skyline, []int{e.X, h}) } } }5.4 排序细节同 x 边界的高度顺序原文档特别强调排序时需要注意的两个问题代码 218. The Skyline Problem.go 的实现完全对应如果大楼边界相等且都是进入状态T 0按高度从大到小排序es[i].H es[j].H保证更高的楼先进入避免低楼先进入产生错误的中间关键点如果大楼边界相等且都是离开状态T 1按高度从小到大排序es[i].H es[j].H保证更矮的楼先离开最高的楼最后离开从而在“移除最高”时得到正确的第二高边界相等但类型不同时进入T 0排在离开T 1之前。这些细节是扫描线解法正确性的关键任何顺序颠倒都会产生重复点或错误的关键点。六、三种解法的正确性验证仓库测试用例仓库为该题提供了完整测试218. The Skyline Problem_test.go覆盖了多种边界场景输入buildings期望输出skyline覆盖场景[[2 9 10],[3 7 15],[5 12 12],[15 20 10],[19 24 8]][[2 10],[3 15],[7 12],[12 0],[15 10],[20 8],[24 0]]题目标准示例[[1 2 1],[1 2 2],[1 2 3],[2 3 1],[2 3 2],[2 3 3]][[1 3],[3 0]]完全重叠楼 边界恰好相接[[4 9 10],[4 9 15],[4 9 12],[10 12 10],[10 12 8]][[4 15],[9 0],[10 10],[12 0]]两簇楼之间有空隙地面为轮廓一部分[][]空输入多栋左边界相同、高度递增的楼[[1 5],[2 6],[3 7],[4 8],[5 9],[10 0]]左边界同点高度递进、输出合并测试函数同时调用getSkyline、getSkyline1、getSkyline2三种解法并打印输入输出另有Test_IndexMaxPQ218专门验证IndexMaxPQ的Remove/sink分支覆盖先移除最大值 8验证Front()变为 7再移除 7 验证变为 6见 218. The Skyline Problem_test.go。七、同类问题串联699 / 715 / 732原文档指出这类问题的相关题目并给出区别这也是面试中举一反三的关键第 715 题Range Module区间更新定值不是增减与本题线段树解法共享“区间取 max”的幂等更新语义第 699 题Falling Squares与本题类似的“俄罗斯方块”类问题线段树离散化时同样要注意右边界处理第 732 题My Calendar III与 699 类似但第 732 题中方块可以“断裂”处理方式略有差异。仓库中对应实现分别位于 0715.Range-Module、0699.Falling-Squares、0732.My-Calendar-III 目录下可作为进阶对比阅读。八、小结LeetCode 218 题的核心不在于“画出轮廓”而在于三类数据结构的灵活运用树状数组解法教会我们当最大值“删除”困难时可以通过反转Query语义前缀 → 后缀让最大值“晚到”从而回避删除操作线段树解法教会我们离散化区间时右边界减一配合幂等 merge 的 lazy 更新SegmentTree.go可以在 O(n log n) 内完成区间覆盖与单点取值扫描线解法教会我们把每个边界建模为 enter/leave 事件后排序顺序同 x 时进入按高到低、离开按低到高与支持按 key 删除的索引最大堆IndexMaxPQ是正确性的两大支柱。三种解法的时间复杂度均为 O(n log n)实际工程中推荐优先掌握扫描线思路因为它直观、可扩展且对后续处理区间动态最值类问题如 715、732有直接帮助。完整的可运行代码、测试与通用模板均已包含在当前仓库中可直接在本地 Go 环境运行验证。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考