发管理工作平时热衷于分享各种编程领域的软硬技能知识以及前沿技术包括iOS、前端、Harmony

OS、Java、Python等方向。

在移动端开发、鸿蒙开发、物联网、嵌入式、云原生、开源等领域有深厚造诣。

图书作者《ESP32-C3

城市天际线问题要求根据给定的建筑物位置和高度计算出从远处看这些建筑物形成的天际线轮廓。

每个建筑物都可以用一个三元组

[lefti,

高效地计算天际线解题过程中会用到优先队列最大堆来动态维护当前最大高度从而生成天际线。

天际线

是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。

给你所有建筑物的位置和高度请返回

天际线

。

关键点是水平线段的左端点。

列表中最后一个点是最右侧建筑物的终点y

坐标始终为

仅用于标记天际线的终点。

此外任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

[...[2

[[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]]

buildings

事件建模首先将每个建筑物的左端点和右端点视为事件。

每个左端点可以看作是一个建筑物的起始位置需要记录该建筑物的高度右端点则表示建筑物结束需要移除该建筑物。

优先队列最大堆利用优先队列最大堆来动态维护当前活跃的建筑物的高度。

每当遇到左端点时将建筑物的高度加入堆中当遇到右端点时将建筑物的高度从堆中移除。

生成关键点通过扫描事件点我们根据当前堆的最大高度来确定天际线的高度。

每当堆的最大值发生变化时记录下新的关键点。

题解代码分析

事件构建将每个建筑物的左端点和右端点作为事件分别表示建筑物的开始和结束。

对于每个事件我们需要记录其横坐标、事件类型左端点或右端点和高度。

优先队列使用最大堆来维护当前的建筑物高度堆的根节点即为当前活跃建筑物的最大高度。

遍历并生成结果按横坐标排序所有事件遍历事件时动态维护堆生成天际线的关键点。

Swift

按照横坐标排序横坐标相同的事件按类型排序左端点优先events.sort

$0.x

通过扫描线算法并结合最大堆数据结构我们可以高效地计算出由多个建筑物形成的城市天际线。

对于每个建筑物的左端点和右端点事件我们利用最大堆来维护当前最大高度并根据高度变化生成关键点。

最终我们得到了天际线的正确轮廓。

这种算法不仅能高效地处理较大规模的输入数据还能保证输出的正确性。

随着建筑物数量和坐标范围的增大这种解法的优势更加突出。

参考资料