# Leetcode 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：

1 2	输入：buildings = [[0,2,3],[2,5,3]] 输出：[[0,3],[5,0]]

提示：

1 <= buildings.length <= 104
0 <= lefti < righti <= 231 - 1
1 <= heighti <= 231 - 1
buildings 按 lefti 非递减排序

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/the-skyline-problem
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

# 解题思路

解答本题使用的是扫描线算法，对于这个题我本来是没什么思路的，后来看了一些教程才有的思路。

扫描线算法，顾名思义就是对线条进行扫描，这里我们扫描的是建筑物的边缘线。

我在这里先简述一下扫描线算法的原理：构造一个大顶堆（优先队列也行），从左到右扫描建筑物，扫描到左边线时，将该建筑物的高度加入大顶堆；扫描到右边线，将当前建筑物的高度弹出大顶堆。在扫描搭配左（右）边线并将当前建筑物的高度加入（弹出）大顶堆之后，我们需要观察大顶堆的最大值有没有发生变化，如果发生变化，则证明产生了关键点，并记录产生的关键点，关键点坐标为 (当前的 x 坐标，大顶堆弹出当前建筑物高度后的最大值)。经过这样的一边扫描之后，我们就可以顺利的得到我们想要的关键点了。

那么，如何区分左边线和右边线呢？这里使用的方法是在读入数据的时候将左边线的纵坐标读入成负值，这样就可以通过纵坐标的正负来判断扫描到的线是左边线还是右边线了。

在读入数据结束后，我们需要使用 sort 函数对数据进行升序排序，以确保：

我们是从左到右来扫描边线
我们扫描边线碰到某条左边线和某条右边线重合的情况时，先对左边线进行扫描，再扫描右边线（因为录入信息的时候将左边线的纵坐标录入为负值，在 sort 排序时横坐标相同的情况下左边线靠前，从而可以先进行扫描）
两条左边先重合时让高度高的线进入大根堆
两条右边线重合时高度小的先弹出大根堆

这样，在扫描结束后我们就可以得到想要的关键点集合了

# 代码实现

C++ multiset

(133 条消息) multiset 用法总结__CSDN

C++ Multiset | Tutorials on Top 27 Multiset Functions with Examples (educba.com)

class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {

        vector<pair<int,int>> vec;
        // auto& 会修改 buildings 里面的元素
        for(auto& b: buildings) {
            vec.push_back({ b[0], -b[2] });
            vec.push_back({ b[1], b[2] });
        }
        sort(vec.begin(),vec.end());

        // multiset当大顶堆的用
        multiset<int> pq;
        // 初始化 先放一个0
        pq.insert(0);
        int preMax = 0;

        // 关键点存放
        vector<vector<int>> res;
        for (auto& p : vec) {
            // 遇到左边线
            if (p.second < 0) {
                pq.insert(-p.second);
            }
            // 遇到右边线
            else {
                pq.erase(pq.find(p.second));
            }
            // 获取当前最大值
            int curMax = *pq.rbegin();
            // 判断是否为关键点
            if (curMax != preMax) {
                // 放入关键点集合并更新最大值
                res.push_back({ p.first,curMax });
                preMax = curMax;
            }
        }
        return res;
    }
};