skyline problem
今天leetcode的每日一题，感觉是一道很不错的题，所以拿出来分享一下
还有一篇讲的不错的文章 链接
这种问题的解法总是一步一步迭代出来的，这里我打算讲一种思路，三个实现方法
首先我们可以考虑一种很暴力的解法，就是从左到右枚举每一个横坐标（注意是离散化后的），然后枚举每一个矩形，判断能够包含这个横坐标的最大的矩形高度是多少，这样我们就可以确定这个关键点的纵坐标了
可以想到，我们枚举横坐标是一个必须的过程，因为我们最终要求出所有的关键点。但是我们不必每次都枚举所有的矩形，只要枚举和我当前横坐标有关的矩形就可以
虽然这样的做法复杂度还是n方的，但是这可以启发我们，不一定要在每一个横坐标上枚举矩形，而是利用矩形帮我们更新横坐标
想象现在有一条从左到右的扫描线，他会扫描每一个矩形的边缘。对于每一个边缘来说，我们要么是在集合中添加一个高度，要么是在集合中删除一个高度，即对应了矩形左右边缘。
那么我们对于每一个横坐标，只要找当前集合中的最大值即可
for edge in edges:
if edge is left_edge:
set.insert(edge)
else
set.erase(edge)
height[edge] = set.max_element
根据这个伪代码，我们可以利用c++的multiset来实现这个算法
毕竟multiset底层是平衡树，功能还是比较强大的，并且处理这个问题是十分合适的，所以代码会显得比较简单
那么如果不用平衡树呢，我们就可以用线段树
对于线段树来说，做这道题的思路就更为暴力了一些。我们只需要在离散化后的坐标系中画出这些矩形即可
对于一个矩形，我们在其对应的区间上进行区间赋值，然后对于每一个横坐标来说，我们单点查询这个横坐标的高度即可
注意对于区间赋值的情况，我们希望高的矩形覆盖矮的矩形，所以我们可以用高度较小的矩形开始枚举。这样就不需要在赋值的时候考虑最值的问题了。
那么如果我们不用线段树呢？就需要我们回到扫描线的思路中，维护最值的还有一个很好用的数据结构就是堆，或者叫优先队列
但是优先队列无法满足可以直接删除某一个元素的操作，这样我们可以在插入矩形高度的同时，插入对应矩形的右边缘，用来记录该高度何时失效。
在枚举到某一个横坐标的时候，我们可以查看优先队列中的队首元素，如果该元素的横坐标小于我们当前的坐标，表示该高度已经失效，我们就将其pop出来
所以根本思路实际上是利用横坐标来进行了一个延迟删除。这样保证了维护高度的正确性，算法正确性也就得到了保证
文章评论