本文发布且更新于个人博客：https://www.xerrors.fun /leetcode/the-skyline-problem/
1. 题目
城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。现在，假设您获得了城市风光照片（图A）上显示的所有建筑物的位置和高度，请编写一个程序以输出由这些建筑物形成的天际线（图B）。
链接：https://leetcode-cn.com/problems/the-skyline-problem
例如，图A中所有建筑物的尺寸记录为：[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ]。
输出是以[ [x1,y1], [x2, y2], [x3, y3], ... ]格式的“关键点”（图B中的红点）的列表，它们唯一地定义了天际线。关键点是水平线段的左端点。请注意，最右侧建筑物的最后一个关键点仅用于标记天际线的终点，并始终为零高度。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。
例如，图B中的天际线应该表示为：[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]。
说明:
- 任何输入列表中的建筑物数量保证在
[0, 10000]范围内。 - 输入列表已经按左
x坐标Li进行升序排列。 - 输出列表必须按
x位排序。 - 输出天际线中不得有连续的相同高度的水平线。例如
[...[2 3], [4 5], [7 5], [11 5], [12 7]...]是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[...[2 3], [4 5], [12 7], ...]
2. 解题思路
开始的思路
思路其实很容易想到，就像是一条流水线一样，拿着一根垂直线沿着X轴方向移动，每一个时刻都判断当前建筑的最高的那个建筑的高度，跟上一个时刻的最高的高度相比，如果不一样那么就代表这个点是一个关键点。
同时，把当前时刻的建筑保存在一个数组里面，方法是需要在每一个时刻都检查是否有新的建筑进入数组，之后需要检查是否有建筑结束了。
但是恐怖就在于，超时了，这里引用一位网友的话：
自行优化
这时候来分析一下这个用例的特点：这个建筑特别大，特别高，只有一个。所以就是说我们在每一个时刻都要判断是都有新的建筑以及是否有建筑被删除，然后在这个例子里面，这些判断都是徒劳的，只有一个建筑。所以优化的方向就是不要对这些无用点进行检测，所以采用的办法就是把原本的扫描点替换成有意义的点，也就是建筑物的边缘点：
points = []
for k in buildings:
if k[0] not in points:
points.append(k[0])
if k[1] not in points:
points.append(k[1])
points.sort()
但是，新的问题就出现了，[[1,2,1],[1,2,2],[1,2,3]] 这个例子的特点是三个建筑物重叠但是高度不一样，按理说应该不是问题，但是出现了一个意想不到的错误，那么是遍历删除的时候出现的错误；当我们的扫描线到达点 2 的时候，这三个建筑都应当从数组中删除，但是：
for build in q:
if build[1] <= points[i]:
q.remove(build)
这个方法删除元素的时候，并不能够删除所有元素，比如下面这个例子：
a = [1, 2, 3 ,4, 5, 6]
for i in a:
if i > 0:
a.remove(i)
print(a)
# [2, 4, 6]
所以这时候采用过滤的办法来解决这个问题：
q = list(filter(lambda x: x[1] > points[i], q))
此时完整的代码：
class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
q = []
res = []
i, j, cur_height = 0, 0, 0
m = len(buildings)
points = []
for k in buildings:
if k[0] not in points:
points.append(k[0])
if k[1] not in points:
points.append(k[1])
points.sort()
while True:
# 添加新来的建筑
while j != m and buildings[j][0] == points[i]:
q.append(buildings[j])
j += 1
# 判断是否结束
if j == m and not q:
break
temp = 0
# 清除已经过去的建筑
q = list(filter(lambda x: x[1] > points[i], q))
# 检测当前点最高的建筑
for build in q:
temp = max(temp, build[2])
if temp != cur_height:
cur_height = temp
res.append([points[i], temp])
i += 1
return res
然而，又超时了，你看看这例子，是人干的事不：
我瞬间感觉到了我这个算法的绝望，扫描线每一次都要对这么多建筑进行扫描，还能优化啥？？？？
借鉴大佬的思路
最终还是打算借鉴一下大佬的思路，这个算法的思路跟我的最不一样的地方：
- 保存了所有的点，包括相同的左端点以及右端点，同时可以对左右端点进行识别；
- 使用堆的数据结构来保存当前的建筑的高度，可以更快的找到最高的建筑的高度，这也是我上面的算法出现超时的主要原因。
- 所有的点的排序巧妙的使用了负数高度这样一个情况。
3. 最终代码以及运行结果
所以对我的代码进行了修改：
import heapq
class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
# 保存所有的点
points = []
for build in buildings:
points.append((build[0], -build[2]))
points.append((build[1], build[2]))
points.sort(key=lambda x: (x[0], x[1]))
# 用来保存当前扫描线所经过的建筑的高度，用堆来表示
heights = []
res = []
# 因为在堆里面删除元素需要更多的时间开销，所以先把需要删除的元素保存起来
should_del = {}
# 保存当前的高度
cur_height = 0
for point in points:
if point[1] < 0: heapq.heappush(heights, point[1])
elif should_del.get(point[1]):
should_del[point[1]] += 1 # 保存需要删除的次数，删除的时候，删除一次
else:
should_del[point[1]] = 1
# 如果当前堆顶元素是应该删除的元素就先删除掉
while heights and -heights[0] in should_del:
temp = -heights[0]
heapq.heappop(heights)
should_del[temp] -= 1
if should_del[temp] == 0:
should_del.pop(temp)
maxH = -heights[0] if heights else 0
if maxH != cur_height:
cur_height = maxH
res.append([point[0], cur_height])
return res
转载：https://blog.csdn.net/jaykm/article/details/106873336