Leecode218：天际线问题

题目链接 [2021_07_13]
联想到的题型：方法——优先队列进行优化求解
会议室II

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

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

lefti 是第 i 座建筑物左边缘的 x 坐标。
righti 是第 i 座建筑物右边缘的 x 坐标。
heighti 是第 i 座建筑物的高度。
天际线 应该表示为由 “关键点” 组成的列表，格式 [[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：

输入：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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：
暴力法：
使用O(n)地枚举建筑的每个边缘作为关键点的横坐标，过程中我们 O(n)O(n) 地检查每一座建筑是否「包含该横坐标」，找到最大高度，即为该关键点的纵坐标。该算法的时间复杂度是 O(n*n)
优化： 使用优先队列来优化寻找最大高度的时间，在从左到右枚举横坐标的过程中，实时的更新优先队列。这样无论如何，优先队列的队首元素即为最大高度。为了维护优先队列，我们应该使用 延时删除 的技巧。无需每次横坐标改变就立刻将优先队列中所有不符合条件的元素都删除，而只需要保证优先队列的队首元素「包含该横坐标」即可。
**注意特殊情况下：**在部分情况下，当横坐标为右边缘时，对于唯一的建筑对其纵坐标没有贡献。因此该横坐标对应的纵坐标的大小为0。

/*
时间复杂度：O(nlogn),其中n为建筑数量。每座建筑至多需要入队出队一次，单次时间复杂度为O(nlogn)
空间复杂度：O(n),其中n为建筑数量，数组boundaries和优先队列的空间占用均为O(n)
*/
class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        //区间内取最大的问题，有点类似那个会议室
        //10 15 15  12 0 10 8 0
        //[0，10][3,15][7,12][12,0][15,10][20,8][24,0]
        //lambada表达式，是优先队列以结束点从小到大排列；优先队列que
        auto cmp = [](const pair<int, int>& a, const pair<int, int>& b)->bool{return a.second < b.second;};
        //decltype推出匿名类的类型
        priority_queue<pair<int, int>, vector<pair<int,int>>, decltype(cmp)> que(cmp);
        //将所有边界点放入boundaries中
        vector<int> boundaries;
        for(auto& building : buildings)
        {
            boundaries.emplace_back(building[0]);
            boundaries.emplace_back(building[1]);
        }
        //默认以第一位数字进行从小到大的排序
        sort(boundaries.begin(), boundaries.end());

        vector<vector<int>> ret;
        int n = buildings.size(), idx = 0;
        //遍历每个端点
        for(auto& boundary : boundaries)
        {
            while(idx < n && buildings[idx][0] <= boundary)
            {
                que.emplace(buildings[idx][1] , buildings[idx][2]);
                idx++;
            }
            //如果端点已经出了队列中的端点了，就将该端点直接移除
            while(!que.empty() && que.top().first <= boundary){
                que.pop();
            }
            int maxn = que.empty() ? 0 : que.top().second;
            //如果ret原始为空，或者当前的最大值不等于上一个的最大值，也就是maxn不作为上一个的延长线，
            if(ret.size() == 0 || maxn != ret.back()[1])
            {
                ret.push_back({boundary, maxn});
            }
        }   
        return ret;
    }
};