天际线问题

题目

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

每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [left_i, right_i, height_i] 表示：

left_i 是第 i 座建筑物左边缘的 x 坐标。
right_i 是第 i 座建筑物右边缘的 x 坐标。
height_i 是第 i 座建筑物的高度。
你可以假设所有的建筑都是完美的长方形，在高度为 0 的绝对平坦的表面上。

天际线 应该表示为由 “关键点” 组成的列表，格式 [[x₁,y₁],[x₂,y₂],...] ，并按 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：

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

提示：

1 <= buildings.length <= 10⁴
0 <= left_i < right_i <= 2³¹ - 1
1 <= height_i <= 2³¹ - 1
buildings 按 left_i 非递减排序

思路

每一个关键点都是最高高度发生变化的点，从左到右遍历高度，记录当前最高高度和前一个最高高度，

比较两者，看是否发生变化，如果变化，则找到一个关键点。而关键点都是某一个建筑物的左边缘或右边缘，

所以要遍历每一个建筑物的left_i和right_i，看此时的最高高度有没有发生变化。

而记录最高高度的数据结构就很重要了。记这个数据结构为ds，遍历建筑物时，ds可能需要插入高度，查找高度，

删除高度。还可能存在两个高度相同的情况。还需要得到最高高度。而c++中的multset，刚好满足这个需求。

直接遍历buildings是不行的，因为常常存在后一个建筑物的left_i位于前一个建筑物的left_i

和right_i之间，在坐标轴上有直观的表示。所以要对buildings做处理，处理成每一个建筑物的left_i

right_i按照从小到大的顺序排列。然后再遍历。而每一栋建筑物的高度，在left_i时进入ds，在

right_i时出ds。这个也很好理解，使用扫描线从左到右扫描，扫描线遇到left_i，进入建筑物，

遇到right_i，离开建筑物。

代码

class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        multiset<pair<int, int>> all;
        vector<vector<int>> res;
        
        for (auto& e : buildings) {
            all.insert(make_pair(e[0], -e[2])); // 每个建筑物的左边角
            all.insert(make_pair(e[1], e[2])); // 每个建筑物的右边角
        }
        
        multiset<int> heights({0}); // 保存当前位置所有高度。
        vector<int> last = {0, 0}; // 保存上一个位置的横坐标以及高度
        for (auto& p : all) {
            if (p.second < 0) heights.insert(-p.second); // 左端点，高度入堆
            else heights.erase(heights.find(p.second)); // 右端点，移除高度
            
            // 当前关键点，最大高度
            auto maxHeight = *heights.rbegin();
            
            // 当前最大高度如果不同于上一个高度，说明这是一个转折点
            if (last[1] != maxHeight) {
                // 更新 last，并加入结果集
                last[0] = p.first;
                last[1] = maxHeight;
                res.push_back(last);
            }
        }
        
        return res;
    }
};