【优先队列+STL】218. 天际线问题（hard）——详细思路解析

1、题目再现

218. 天际线问题

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

每个建筑物的几何信息由数组 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、思路分析

笔者查阅各类型的题解，发现对该题目中的解题过程仍然还是搞不清楚，终于找到了一篇较为清晰的文章，其描述的算法浅显易懂，本文就是基于此题解做出的更近一步的分析和阐述。

参考文章：详细通俗的思路分析，多解法

在这里插入图片描述
上图给出了示例中的天际线线路，可以发现，所谓的关键点只不过都来自于每个building的左上和右上端点，所以说，首先的思路是将左右每个building的左右端点提取出来，然后进行下一步的操作。

以示例中的数据为例，我们得到了所有建筑的左右端点：并做了左右的标记
l(2,10) r(9,10) l(3,15) r(7,15) l(5,12) r(12,12)
l(15,10) r(20,10) l(19,8) r(24,8)

再次回到上图，我们发现关键点的位置存在一个共性：如果是上升的，那么关键点一定是在上升过程中的最高点（左端点）；如果是下降的，关键点在下降过程中的次高点。（右端点）
在这里插入图片描述
好的，那么我们可以看到，如果下一个左端点比当前所保存的所有的高度都大，那么其所在位置一定是关键点。如果走到了右端点，则说明该buildings的区域已经扫描完毕了，需要将之前保存的该点的高度删除掉！

从这里也能看出，需要设计一个数据结构，每次都能保存所有的高度，并且能返回所有高度中的最大值，优先队列刚好符合这种特性！！！

因此，整个算法的思路大致如下：

1、只考虑每个 building 的左上角和右上角坐标，将所有点按 x 坐标排序，然后开始遍历。

2、需要一个优先队列来存储遍历坐标的高度，也就是 y 轴坐标。对于左上角坐标和右上角坐标有不同的处理方式。

3、遇到左上角坐标，将其 y 坐标加入到优先队列中。

4、遇到右上角坐标，将其 y 坐标从优先队列中删除，也就是删除了其对应的左上角坐标的 y 值。

5、最后判断优先队列中的最高高度相对于之前是否更新，如果更新了的话，就将当前的 x 以及更新后的最高高度作为一个坐标加入到最终结果中。

将该算法过程使用示例进行测试：

buildings  [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8]
根据 buildings 求出每个 building 的左上角和右上角坐标
将所有坐标按照 x 排序, 并标记当前坐标是左上角坐标还是右上角坐标
l(2,10) l(3,15) l(5,12) r(7,15) r(9,10) r(12,12) 
l(15,10) l(19,8) r(20,10) r(24,8)
PriorityQueue = {0}, preMax = 0

l(2,10) 将 10 加入优先队列
preMax = 0, PriorityQueue  = {0 10}
当前 PriorityQueue 的 max = 10, 相对于 preMax 更新了
将 (2,10) 加入到 res, res = {(2,10)}
更新 preMax = 10
    
l(3,15) 将 15 加入优先队列
preMax = 10, PriorityQueue  = {0 10 15}
当前 PriorityQueue 的 max = 15, 相对于 preMax 更新了
将 (3,15) 加入到 res, res = {(2,10) (3,15)}
更新 preMax = 15    
    
l(5,12) 将 12 加入优先队列
preMax = 15, PriorityQueue  = {0 10 15 12}
当前 PriorityQueue 的 max = 15, 相对于 preMax 没有更新
res 不变

r(7,15) , 遇到右上角坐标, 将 15 从优先队列删除
preMax = 15, PriorityQueue  = {0 10 12}
当前 PriorityQueue 的 max = 12, 相对于 preMax 更新了
将 (7,max) 即 (7,12) 加入到 res, res = {(2,10) (3,15) (7,12)}
更新 preMax = 12
    
r(9,10) , 遇到右上角坐标, 将 10 从优先队列删除
preMax = 12, PriorityQueue  = {0 12}
当前 PriorityQueue 的 max = 12, 相对于 preMax 没有更新
res 不变

r(12,12) , 遇到右上角坐标, 将 12 从优先队列删除
preMax = 12, PriorityQueue  = {0}
当前 PriorityQueue 的 max = 0, 相对于 preMax 更新了
将 (12,max) 即 (7,0) 加入到 res, res = {(2,10) (3,15) (7,12) (12,0)}
更新 preMax = 0
    
后边的同理，就不进行下去了。

然后再考虑一些边界情况，开始给坐标排序的时候我们是根据 x 坐标大小，当 x 坐标相等的时候怎么办呢？

考虑两个坐标比较的时候，x 坐标相等会有三种情况。

当两个坐标都是左上角坐标，我们要将高度高的排在前边
当两个坐标都是右上角坐标，我们要将高度低的排在前边
当两个坐标一个是左上角坐标，一个是右上角坐标，我们需要将左上角坐标排在前边

上边的三条规则也是根据三种情况归纳总结出来的，大家可以举例子来判断。

有了这三个规则，然后写代码的话就会很繁琐，这里有个技巧。存左上角坐标的时候，将高度（y）存为负数。存右上角坐标的时候，将高度（y）存为正数。

这么做有两个作用。

一个作用就是可以根据高度的正负数区分当前是左上角坐标还是右上角坐标。

另一个作用就是可以通过一个比较器，就实现上边的三条比较规则。

3、STL——multiset的使用

虽然stl中有专门的优先队列数据结构——priority_queue，但是本题中涉及到对队列元素中按值删除操作，在该类型下无法完成！但是multiset数据结构可以实现上述功能，具体的使用方法参照下面的博客吧。
multiset用法总结

4、代码c++

class Solution {
public:
    static bool cmp(pair<int,int> a,pair<int,int> b){
        int xa = a.first;
        int ya = a.second;
        int xb = b.first;
        int yb = b.second;
        if(xa != xb){
            return xa<xb;
        }
        else{
            return ya<yb;
        }
        
    }
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        vector<pair<int,int>> points;
        for(int i = 0;i<buildings.size();i++){
            int x = buildings[i][0];
            int y = buildings[i][1];
            int height = buildings[i][2];
            points.push_back(make_pair(x,-height));
            points.push_back(make_pair(y,height));
        }
        sort(points.begin(),points.end(),cmp);
        multiset<int,greater<int>> q;
        q.insert(0);
        int preMax = 0;
        vector<vector<int>> ans;
        for(int i = 0;i<points.size();i++){
            int x = points[i].first;
            int y = points[i].second;
            //  左端点
            if(y < 0){
                q.insert(-y);
                if(preMax != *(q.begin())){
                    preMax = *(q.begin());
                    ans.push_back({x,-y});
                }
            }
            //  右端点
            else{
                q.erase(q.find(y));
                if(preMax != *(q.begin())){
                    preMax = *(q.begin());
                    ans.push_back({x,preMax});
                }
            }
        }
        return ans;
    }
};