题目描述

城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。现在，假设您获得了城市风光照片（图A）上显示的所有建筑物的位置和高度，请编写一个程序以输出由这些建筑物形成的天际线（图B）。

每个建筑物的几何信息用三元组[Li，Ri，Hi]表示，其中Li和 Ri分别是第i座建筑物左右边缘的x 坐标，Hi是其高度。可以保证 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX 和 Ri - Li > 0。您可以假设所有建筑物都是在绝对平坦且高度为 0 的表面上的完美矩形。


例如，图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], …]

算法1

(线性扫描算法) $O(nlogn)$

题解：我们记录每个大楼的左端点和右端点以及对应的高度，然后使用一条扫描线从左向右扫描，每次遇到一个大楼的左端点或者右端点，就有可能是关键点。很直观我们可以得到以下的判别方式。

如果当前扫描到的点是左端点：如果当前左端点p是当前位置上最高的点，那么这一个点是一个关键点(p.left,p.height)。

如果当前扫描到的点是右端点：如果当前右端点p比除了这个右端点之外最高的点q还要高，那么我们形成了一个关键点，这个关键点的坐标就是(p.right,q.height)。

接下来我们就需要考虑如何能够高效的实现支持单点更新的区间最大值（楼的高度），线段树是可以的，但是这道题也没有区间查询，那么我们直接使用一个multiset就可以了，这里使用multiset而不是set是因为多个建筑物可以共享同一个高度。如果遇到左端点，我们就把这个楼的高度加入multiset；如果遇到右端点，我们就把这个楼的高度从multiset中移除。

为了进行线性扫描算法，我们需要先将所有楼的左顶点和右顶点进行按照横坐标进行排序。我们需要考虑如下情况：

如果同一个横坐标有两个左顶点，我们记做p1.height > p2.height那么高度较高的那个左顶点才是真正的关键点，根据关键点判别思路，我们应该先遍历高度较高的那个p1。

如果同一个横坐标有两个右顶点，我们记做p1.height > p2.height，根据关键点判别思路如果先将高度较高的那个移除，就会生成一个(p1.right,p2.height)的错误关键点。所以我们应该先移除高度较小的右端点p2。

如果同一个横坐标有一个左端点p1和一个右端点p2，如果我们先遍历右端点再遍历左端点，我们可能会得到一个错误的关键点。
综上所述，我们对顶点进行排序，应该是按照横坐标从小到大，横坐标相同时，如果都是左端点，先那么遍历较高的那个，如果是右端点，先遍历较矮的那个，如果一个左端点一个右端点，先遍历左端点。基于这种思想，我们使用pair<int,int>来存储端点，如果是左端点，存储<p.left,-p.height>，如果是右端点存储<p.right,p.height>。pair的比较是先基于第一关键字再急于第二关键字的，可以完美的支持上述比较。

我们的算法如下：

1. 先将所有建筑物的左右顶点加入到events中，使用一个multiset支持排序。

2. 为了处理边界情况先在height中添加一个0。

3. 从左向右遍历每一个event：

如果是左端点，如果其高度大于当前位置最大高度加入答案，同时将高度加入height的multiset。

如果是右端点，先将该高度移除出height，如果其高度高于新的height的最大值，那么是一个关键点。

C++ 代码

    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        vector<vector<int>> res;
        multiset<pair<int,int>> events;
        multiset<int> height;
        height.insert(0);
        int n = buildings.size();
        for(int i = 0 ; i < n ; i ++)
        {
            events.insert(make_pair(buildings[i][0],-buildings[i][2]));
            events.insert(make_pair(buildings[i][1],buildings[i][2]));            
        }
        for(auto p:events)
        { 
            if(p.second < 0)
            {
                if(-p.second > *height.rbegin())
                    res.push_back({p.first,-p.second});
                height.insert(-p.second);
            }
            else
            {
                height.erase(height.find(p.second));
                if(p.second > *height.rbegin())
                    res.push_back({p.first,*height.rbegin()});
            }
        }
        return res;
    }