什么叫网站的空间感,泰安网络电视,php网站伪静态,免费购物的软件网罗开发 #xff08;小红书、快手、视频号同名#xff09; 大家好#xff0c;我是 展菲#xff0c;目前在上市企业从事人工智能项目研发管理工作#xff0c;平时热衷于分享各种编程领域的软硬技能知识以及前沿技术#xff0c;包括iOS、前端、Harmony OS、Java、Python等… 网罗开发 小红书、快手、视频号同名 大家好我是 展菲目前在上市企业从事人工智能项目研发管理工作平时热衷于分享各种编程领域的软硬技能知识以及前沿技术包括iOS、前端、Harmony OS、Java、Python等方向。在移动端开发、鸿蒙开发、物联网、嵌入式、云原生、开源等领域有深厚造诣。
图书作者《ESP32-C3 物联网工程开发实战》 图书作者《SwiftUI 入门进阶与实战》 超级个体COC上海社区主理人 特约讲师大学讲师谷歌亚马逊分享嘉宾 科技博主极星会首批签约作者 文章目录 摘要描述题解答案题解代码分析步骤解析Swift 代码实现 示例测试及结果示例 1示例 2 时间复杂度与空间复杂度总结参考资料 摘要
城市天际线问题要求根据给定的建筑物位置和高度计算出从远处看这些建筑物形成的天际线轮廓。每个建筑物都可以用一个三元组 [lefti, righti, heighti] 表示分别表示建筑物的左边界、右边界和高度。本文将介绍如何使用 Swift 高效地计算天际线解题过程中会用到优先队列最大堆来动态维护当前最大高度从而生成天际线。 描述
城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度请返回 由这些建筑物形成的 天际线 。
每个建筑物的几何信息由数组 buildings 表示其中三元组 buildings[i] [lefti, righti, heighti] 表示
lefti 是第 i 座建筑物左边缘的 x 坐标。righti 是第 i 座建筑物右边缘的 x 坐标。heighti 是第 i 座建筑物的高度。
你可以假设所有的建筑都是完美的长方形在高度为 0 的绝对平坦的表面上。
天际线 应该表示为由 “关键点” 组成的列表格式 [[x1,y1],[x2,y2],...] 并按 x 坐标 进行 排序 。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点y 坐标始终为 0 仅用于标记天际线的终点。此外任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。
注意 输出天际线中不得有连续的相同高度的水平线。例如 [...[2 3], [4 5], [7 5], [11 5], [12 7]...] 是不正确的答案三条高度为 5 的线应该在最终输出中合并为一个[...[2 3], [4 5], [12 7], ...]
示例 1 输入 buildings [[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]]
解释
图 A 显示输入的所有建筑物的位置和高度
图 B 显示由这些建筑物形成的天际线。图 B 中的红点表示输出列表中的关键点。示例 2
输入 buildings [[0,2,3],[2,5,3]]
输出 [[0,3],[5,0]]提示
1 buildings.length 1040 lefti righti 231 - 11 heighti 231 - 1buildings 按 lefti 非递减排序 题解答案
天际线问题是一个典型的扫描线问题我们可以通过以下步骤来解决 事件建模首先将每个建筑物的左端点和右端点视为事件。每个左端点可以看作是一个建筑物的起始位置需要记录该建筑物的高度右端点则表示建筑物结束需要移除该建筑物。 优先队列最大堆利用优先队列最大堆来动态维护当前活跃的建筑物的高度。每当遇到左端点时将建筑物的高度加入堆中当遇到右端点时将建筑物的高度从堆中移除。 生成关键点通过扫描事件点我们根据当前堆的最大高度来确定天际线的高度。每当堆的最大值发生变化时记录下新的关键点。
题解代码分析
步骤解析 事件构建将每个建筑物的左端点和右端点作为事件分别表示建筑物的开始和结束。对于每个事件我们需要记录其横坐标、事件类型左端点或右端点和高度。 优先队列使用最大堆来维护当前的建筑物高度堆的根节点即为当前活跃建筑物的最大高度。 遍历并生成结果按横坐标排序所有事件遍历事件时动态维护堆生成天际线的关键点。
Swift 代码实现
import Foundationfunc getSkyline(_ buildings: [[Int]]) - [[Int]] {var events [(x: Int, h: Int, type: Int)]()for building in buildings {let (left, right, height) (building[0], building[1], building[2])events.append((x: left, h: height, type: 1)) // 左端点事件events.append((x: right, h: height, type: -1)) // 右端点事件}// 按照横坐标排序横坐标相同的事件按类型排序左端点优先events.sort { $0.x $1.x || ($0.x $1.x $0.type $1.type) }var result [[Int]]()var maxHeap [(h: Int, count: Int)]() // (高度, 数量)maxHeap 以高度为优先级模拟最大堆var heightToCount [Int: Int]() // 高度到数量的映射for event in events {let (x, h, type) eventif type 1 { // 左端点heightToCount[h, default: 0] 1} else { // 右端点heightToCount[h, default: 0] - 1}// 更新堆var currentHeight 0for (key, value) in heightToCount {if value 0 {currentHeight max(currentHeight, key)}}if result.isEmpty || result.last![1] ! currentHeight {result.append([x, currentHeight])}}return result
}示例测试及结果
示例 1
let buildings1 [[2,9,10], [3,7,15], [5,12,12], [15,20,10], [19,24,8]]
print(getSkyline(buildings1))
// 输出: [[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]示例 2
let buildings2 [[0, 2, 3], [2, 5, 3]]
print(getSkyline(buildings2))
// 输出: [[0, 3], [5, 0]]时间复杂度与空间复杂度 时间复杂度O(n log n) 排序事件需要 O(n log n) 时间堆操作也需要 O(log n) 时间整体复杂度为 O(n log n)其中 n 是建筑物的数量。 空间复杂度O(n) 存储事件和堆需要 O(n) 的空间n 为建筑物的数量。
总结
通过扫描线算法并结合最大堆数据结构我们可以高效地计算出由多个建筑物形成的城市天际线。对于每个建筑物的左端点和右端点事件我们利用最大堆来维护当前最大高度并根据高度变化生成关键点。最终我们得到了天际线的正确轮廓。
这种算法不仅能高效地处理较大规模的输入数据还能保证输出的正确性。随着建筑物数量和坐标范围的增大这种解法的优势更加突出。
参考资料
LeetCode 题目解答Skyline ProblemSwift 官方文档扫描线算法
