每日算法中，如何理解扫描线算法的基本应用思路？

本文共计3581个文字，预计阅读时间需要15分钟。

题目描述：这是LeetCode上的218. 天际线问题，难度为困难。Tag：扫描线问题、优先队列。城市的天际线是从远处观察该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请输出所有建筑物的天际线。

给定：建筑物的位置和高度。

题目描述

这是 LeetCode 上的 ​​218. 天际线问题​​ ，难度为 困难。

Tag : 「扫描线问题」、「优先队列」

城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回由这些建筑物形成的 天际线 。

每个建筑物的几何信息由数组 ​​buildings​​​ 表示，其中三元组 ​​buildings[i] = [lefti, righti, heighti]​​ 表示：

• ​​left[i]​​ 是第 i 座建筑物左边缘的 x 坐标。
• ​​right[i]​​ 是第 i 座建筑物右边缘的 x 坐标。
• ​​height[i]​​ 是第 i 座建筑物的高度。

天际线 应该表示为由 “关键点” 组成的列表，格式 ​​[[x1,y1],[x2,y2],...]​​，并按 x 坐标 进行 排序 。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y 坐标始终为 0 ，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

注意：输出天际线中不得有连续的相同高度的水平线。