LeetCode-Go 实战解析218. The Skyline Problem天际线问题的线段树与扫描线解法【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本篇文章围绕 LeetCode 第 218 题 The Skyline Problem天际线问题展开完整继承题解文档中的题目定义、输出约束与解题思路并结合 LeetCode-Go 仓库中leetcode/0218.The-Skyline-Problem/目录下的真实实现逐一拆解线段树、树状数组与扫描线三种解法的代码细节与边界处理。读完本文你将掌握关键点key points的定义规则、离散化时右边界必须减一的原因、扫描线事件排序的完整规则以及索引最大堆如何在 O(log n) 内完成插入与删除。题目定义如何用关键点唯一描述一座城市的天际线城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。题目给出了城市风光照片上所有建筑物的位置和高度要求编写程序输出由这些建筑物形成的天际线。每个建筑物的几何信息用三元组[Li, Ri, Hi]表示Li第 i 座建筑物左边缘的 x 坐标Ri第 i 座建筑物右边缘的 x 坐标Hi该建筑物的高度。题目保证0 ≤ Li, Ri ≤ INT_MAX、0 Hi ≤ INT_MAX且Ri - 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], ... ]格式的关键点key points列表它们唯一地定义了天际线。关键点是水平线段的左端点。最右侧建筑物的最后一个关键点仅用于标记天际线的终点高度始终为 0此外任意两个相邻建筑物之间的地面高度 0也应被视为天际线轮廓的一部分。例如图 B 中的天际线表示为[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]输入输出约束题目附带以下说明任何正确解法都必须满足约束说明建筑物数量任何输入列表中的建筑物数量保证在[0, 10000]范围内注意可以为 0即空输入输入顺序输入列表已按左 x 坐标Li升序排列输出顺序输出列表必须按 x 坐标排序等高合并输出天际线中不得有连续的相同高度的水平线。例如[...[2 3], [4 5], [7 5], [11 5], [12 7]...]是不正确答案三条高度为 5 的线应合并为[...[2 3], [4 5], [12 7], ...]解题思路总览从楼挡楼到三种经典解法本题给出的二维数组中每个子数组代表一栋高楼的信息起始坐标、终止坐标、高度要求找到这些高楼的边际点并输出对应的高度信息。仓库题解文档与源码给出了三种实现路径全部位于 218. The Skyline Problem.go 中线段树Segment Tree解法二getSkyline1利用区间最大值 lazy 传播不关心楼挡住楼的情况树状数组Binary Indexed Tree解法一getSkyline对右边界事件做前缀最大值查询扫描线Sweep Line解法三getSkyline2配合索引最大堆维护当前最高高度。三种解法的时间复杂度均为 O(n log n)其中扫描线在事件驱动思路上最为直观。下面逐一展开。解法一线段树 —— 离散化、右边界减一与 lazy 更新用线段树解本题可以完全不用关心楼挡住楼的情况。由于楼的坐标是离散的需要先把楼在 X 轴上的两个坐标离散化。关键细节离散化时右边界必须减一楼的宽度是一个区间但离散化过程中楼的宽度右边界需要减一否则查询一个区间会包含两个点导致错误结果。题解文档给出的例子第一个楼是[1,3)楼高 10第二个楼是[3,6)楼高 20。第一个楼如果算上右边界 3查询[1,3]的结果是 20因为[3,3]这个点会查询到第二个楼上面去。因此每个楼的右边界应该减一。但同时每个楼的右边界也要加入离散化坐标因为最终查询的结果需要包含这些边界。仓库中的discretization218函数正是这么实现的218. The Skyline Problem.gofunc discretization218(positions [][]int) (map[int]int, []int) { tmpMap, posArray, posMap : map[int]int{}, []int{}, map[int]int{} for _, pos : range positions { tmpMap[pos[0]] // 左边界 tmpMap[pos[1]-1] // 右边界减一 tmpMap[pos[1]] // 右边界本身也要加入 } for k : range tmpMap { posArray append(posArray, k) } sort.Ints(posArray) for i, pos : range posArray { posMap[pos] i } return posMap, posArray }可以看到每个楼贡献了三个关键坐标pos[0]左边界、pos[1]-1右边界内最后一个点、pos[1]右边界本身。区间更新与逐点查询离散化得到坐标映射posMap和有序坐标数组pos后getSkyline1复用仓库 template/SegmentTree.go 中实现的懒标记线段树源码位置func 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 }要点线段树的merge函数取max初始化数据全为 0即地面高度 0对每栋楼调用st.UpdateLazy(posMap[b[0]], posMap[b[1]-1], b[2])把区间[左边界, 右边界-1]的高度更新为当前楼高取 max 语义之后依次查询每个离散坐标点的单点高度当前区间高度与前一个区间高度相同则视为等高跳过高度与前一个不同则记录为天际线边缘点。这正对应题解文档中的描述将离散的数据排序以后按照楼的信息每个区间依次 update。最后统计的时候依次统计每个区间如果当前区间的高度和前一个区间的高度一样就算是等高的楼。当高度与前一个高度不相同的时候就算是天际线的边缘就要添加到最后输出数组中。底层支撑template 包中的懒标记线段树template/SegmentTree.go 中的SegmentTree结构体包含data, tree, lazy三个数组merge作为可注入的合并函数定义。UpdateLazy与QueryLazy在下推 lazy 标记时对幂等 merge如 max/min整段套用一次即可做到 O(1) 下推注释说明代码注释里也特别提醒如果改用区间求和 区间加语义则需替换为(right-left1) * lazy的写法。这解释了为什么本解法中区间更新与查询均为 O(log n)。解法二树状数组 —— 事件点上的前缀最大值题解文档提到动态插入并查找最大值可选的数据结构有最大堆和二叉搜索树而仓库中还提供了一种基于树状数组Binary Indexed Tree的解法一getSkyline源码位置。该解法的核心思路为每个楼生成两个事件点Point{xAxis, side, index}其中side为LEFTSIDE 1表示左边界、RIGHTSIDE 2表示右边界对所有事件点按xAxis升序、xAxis相同时按side升序排序左边界事件排在右边界事件之前扫过每个事件点时若为左边界则在该楼右边界对应的事件索引处用bit.Add写入楼高取 max用bit.Query(kth[pt] 1)查询当前位置的前缀最大值即为当前 x 坐标处的天际线高度若与上一个输出点高度不同则记录若 x 相同则就地覆盖高度。其中BinaryIndexedTree在本题文件内自定义实现定义Add从index向前推进index - index -indexQuery从index向后推进index index -index与 template/BIT.go 中标准求和语义的方向相反从而把插入高度、查询前缀最大值转换为树状数组上的 max 操作。解法三扫描线 —— 事件驱动 索引最大堆题解文档明确指出这一题用线段树做时间复杂度有点高可以用扫描线解题并给出了扫描线的思路用一根根垂直于 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()]这段伪代码也被原样保留在 Go 源码的注释中218. The Skyline Problem.go。数据结构选择为什么用索引最大堆题解文档比较了两种候选数据结构数据结构查找 max插入按 key 删除最大堆O(1)O(log n)O(n)且需自己实现二叉搜索树O(log n)O(log n)O(log n)标准最大堆的remove_by_key需要 O(n) 线性扫描因此仓库实现了索引最大堆IndexMaxPQ实现用items存值、pq存堆序、qp维护 key → 堆位置的映射从而支持Front()O(1) 获取当前最高高度堆空时返回 0即地面Enque(key, val)O(log n) 插入并上浮Remove(key)O(log n) 按编号删除并下沉。事件排序规则进入与离开的优先级扫描线正确性的另一关键是事件排序。题解文档特别强调排序的注意点如果大楼的边界相等并且是进入状态那么再按照高度从大到小排序如果大楼的边界相等并且是离开状态那么高度按照从小到大排序。源码中的比较函数完整实现了这一规则排序逻辑先比 xx 相同比类型T0 进入 1 离开类型同为进入时高度降序es[i].H es[j].H类型同为离开时高度升序es[i].H es[j].H。扫描过程getSkyline2的主体源码pq : NewIndexMaxPQ(size) for _, e : range es { curH : pq.Front() if e.T 0 { // enter if e.H curH { skyline append(skyline, []int{e.X, e.H}) } pq.Enque(e.N, e.H) } else { // leave pq.Remove(e.N) h : pq.Front() if curH h { skyline append(skyline, []int{e.X, h}) } } }进入事件若楼高大于当前最高说明它是新的天际线轮廓点记录随后入堆。离开事件移除该楼后若最高高度下降了curH h说明产生了新的较低轮廓线记录第二高h——这与伪代码中移除当前最高的剩下的最高者就是第二高完全一致。测试用例验证五种输入场景全覆盖仓库配套的 218. The Skyline Problem_test.go 对三种解法getSkyline、getSkyline1、getSkyline2同时执行了 5 组测试测试输入期望输出覆盖场景[[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]]左边界相同、结束点产生高度 0[][]空输入7 栋同终点、递增高度的楼[[1,5],[2,6],[3,7],[4,8],[5,9],[10,0]]连续爬升后统一归零此外还单独测试了IndexMaxPQ的Remove/Front行为Test_IndexMaxPQ218验证堆顶元素被反复删除后sink下沉逻辑的正确性。可运行仓库根目录的gotest.sh脚本执行全部测试。延伸同一套数据结构家族的姊妹题题解文档在结尾指出类似的线段树题目还有第 715 题、第 732 题与第 699 题并给出了区分要点715. Range Module区间更新定值不是增减218. The Skyline Problem可以用扫描线732. My Calendar III与 699 题类似也是俄罗斯方块类题目但 732 题的方块会断裂699. Falling Squares掉落方块堆叠高度问题同样依赖离散化 区间最大值仓库中 0699.Falling-Squares/README.md 有完整讲解。这些题目共享仓库 template/SegmentTree.go 与 template/BIT.go 中的通用数据结构实现掌握 218 题的离散化与 lazy 更新套路后可以平滑迁移到其余几题。小结输出形态天际线由水平线段的左端点key points唯一刻画末尾点高度恒为 0且不允许连续等高线线段树解法离散化时右边界减一避免区间重叠误查右边界本身仍入坐标表区间UpdateLazy 逐点QueryLazy比较lastHeight去重树状数组解法将左右边界转为事件点在右边界处写入高度、前缀查询取 max扫描线解法事件enter/leave 索引最大堆进入时记录新高、离开时移除后记录次高同 x 排序规则为进入按高度降序、离开按高度升序。通过 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考