C++ 天际线问题

引言

天际线问题 是一个经典的算法挑战，它涉及找到由二维平面上的一系列矩形建筑物形成的轮廓或“天际线”。想象一个城市景观，其中每个建筑物都由一个矩形表示，由其左侧 x 坐标、高度和右侧 x 坐标定义。问题的目标是计算从远处看时城市的轮廓天际线，其中只有重叠建筑物的最高部分可见。

方法 1：简单方法

实施

输出

 
Skyline: [2, 10] [3, 15] [7, 12] [12, 0] [15, 10] [20, 8] [24, 0]   

说明

步骤 1：将建筑物表示为事件

首先，每个建筑物都由两个关键点表示

• 建筑物开始的起点。
• 建筑物结束的终点。

这些点被视为“事件”。每个事件包括

• x 坐标（x 轴上的位置）。
• 建筑物的高度。
• 事件是建筑物的开始还是结束。

步骤 2：对事件进行排序

接下来，所有事件都根据它们的 x 坐标进行排序。这种排序至关重要，因为它允许我们按照从左到右的正确顺序处理建筑物，就像您在地平线上看到它们一样。有一些特殊情况需要处理

• 如果两个事件具有相同的 x 坐标，则开始事件在结束事件之前处理。这是因为在新建筑物在特定点开始时，可能会抬高天际线，这需要在考虑任何在该点结束的建筑物之前进行处理。
• 如果两个开始事件共享相同的 x 坐标，则先处理较高的建筑物，因为它对天际线的影响更大。
• 类似地，如果两个结束事件共享相同的 x 坐标，则先考虑较短的建筑物，以准确反映高度的过渡。

步骤 3：使用最大堆管理高度

• 为了跟踪当前正在考虑的建筑物的高度（即，已经处理了其开始但尚未达到其结束的建筑物），使用最大堆（或优先队列）。这种数据结构可以高效地让我们始终知道活动建筑物中的当前最大高度。
• 当遇到开始事件时，建筑物的高度被添加到堆中。此高度表示天际线当前最大高度的候选。
• 当遇到结束事件时，这意味着建筑物在此点结束。这里的挑战是从堆中移除建筑物的高度。由于直接从堆中消除元素并不简单，因此一种解决方法是移除所有元素并重新插入那些仍然活动（尚未结束）的元素以更新堆。

步骤 4：记录关键点

处理每个事件后，算法会检查堆中的当前最大高度

• 如果此高度与先前记录的高度不同，则意味着在此 x 坐标处天际线发生了变化。此差异表示一个新的关键点，它标志着天际线轮廓的过渡。

步骤 5：构建天际线

结果是描述天际线的一系列关键点。每个关键点对应于天际线高度发生变化的 x 坐标。通过连接这些关键点，可以绘制出天际线的完整轮廓，表示从远处看到的所有建筑物的最高点。

复杂度分析

时间复杂度

事件创建

• 对于每个建筑物，创建两个事件（开始和结束）。
• 如果有 n 个建筑物，则此步骤涉及 O(n)

事件排序

• 事件根据它们的 x 坐标进行排序，这需要 O(n log n) 时间。排序是计算成本最高的步骤。

事件处理

• 对于每个事件，高度要么添加到最大堆中，要么从最大堆中移除。
• 堆中的插入和删除操作都需要 O(log n) 时间。
• 由于有 2n 个事件，处理所有事件需要 O(2n log n)，简化为 O(n log n)。

因此，总体时间复杂度为 O(n log n)，主要由排序步骤和堆操作决定。

空间复杂度

存储事件

• 算法存储 2n 个事件（每个建筑物两个）。
• 这需要 O(2n) 空间，简化为 O(n)。

最大堆

• 堆中在任何时候最多可以包含 n 个高度，因为所有建筑物都可能重叠。
• 堆所需的空间为 O(n)。

结果存储

• 结果（存储天际线的关键点）在最坏情况下最多可以有 2n 个点（当每个建筑物都添加一个新的关键点时）。
• 这需要 O(n) 空间。

综合这些因素，总体空间复杂度为 O(n)。

方法 2：使用分治法

这种方法受到归并排序算法的启发，通过递归地将问题分解为更小的子问题，然后组合它们的结果以形成最终的天际线。

实施

输出

 
Skyline: [2, 10] [3, 15] [7, 12] [12, 0] [15, 10] [20, 8] [24, 0]    

说明

步骤 1：对建筑物进行排序

在深入研究分治法之前，建筑物会根据它们的左边缘（x 坐标）进行排序。这种排序确保我们以从左到右的顺序处理建筑物，这对于稍后正确合并天际线至关重要。

步骤 2：分解问题

分治法的核心思想是将问题分解为更小的子问题。工作原理如下

• 基本情况： 如果当前段中只有一个建筑物，则该段的天际线由两个关键点组成：建筑物以其高度开始的点和建筑物以零高度结束的点。这很简单，因为没有其他建筑物需要考虑。
• 递归分解： 如果有多个建筑物，则将列表分为两半。这种分解会递归地继续，直到每个段只包含一个建筑物。递归函数将处理这些较小的段，最终将问题分解为可管理的部分。

步骤 3：解决子问题

对于每个段，算法都会计算天际线。当段减少到单个建筑物时，天际线只是该建筑物的起点和终点。然后使用这些简单的天际线来构建更复杂的解决方案。

步骤 4：合并天际线

一旦计算出左右两半的天际线，就需要将它们合并以形成组合段的连续天际线。这通过以下步骤完成

• 初始化指针： 使用指针遍历左右两半的天际线。
• 比较高度： 在每个 x 坐标处，比较左右天际线的高度。确定该 x 坐标处的最大高度并更新生成的天际线。
• 更新结果： 如果高度与前一个 x 坐标不同，则表示天际线中出现了一个新的关键点。将此新关键点添加到结果中。
• 继续合并： 继续此过程，直到处理完两个天际线的所有点。

步骤 5：合并结果

合并过程有效地将两个部分天际线合并为一个单一的、连贯的天际线。通过递归地划分建筑物列表，计算每个段的天际线，并合并这些结果；整个天际线由较小的部分构建。

复杂度分析

时间复杂度

排序

• 操作：根据建筑物的左边缘对建筑物进行排序。
• 复杂度：O(n log n)
• 解释：这是因为排序需要比较和排序每个建筑物，其中 n 是建筑物的数量。

递归分解

• 操作：递归地将建筑物列表分解为较小的段，直到每个段有一个建筑物。
• 复杂度：O(log n) 递归级别。
• 解释：递归树的深度是建筑物数量的对数。

合并

• 操作：合并两个天际线。
• 复杂度：每次合并 O(n)。
• 解释：在合并过程中，每个建筑物段都线性处理以比较和组合天际线。由于大约有 log n 个递归级别，并且每个级别处理总共 n 个元素，因此合并总共需要 O(n log n)。

总时间复杂度： O(n log n)。最重要的因素是分治过程中的排序和合并。

空间复杂度

建筑物事件的存储

• 操作：存储建筑物及其相应的事件。
• 复杂度：O(n)
• 解释：每个建筑物生成两个事件（开始和结束），因此所需的存储空间与建筑物数量成比例。

递归调用堆栈

• 操作：分治过程中递归栈使用的空间。
• 复杂度：O(log n)
• 解释：递归栈的深度是建筑物数量的对数。

合并结果的存储

• 操作：存储合并产生的天际线点。
• 复杂度：O(n)
• 解释：生成的天际线点最多与建筑物数量呈线性关系。

总空间复杂度： O(n)。主要空间使用来自存储建筑物事件和合并结果，以及递归栈的对数空间。