leetcode 困难 —— 天际线问题（优先队列）

（思路感觉挺明显的，就是一些特殊情况得考虑清楚）

题目：
城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回 由这些建筑物形成的 天际线 。
每个建筑物的几何信息由数组 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], …]

题解：
这道题，主要就是和位置，高度相关

① 那我们如果不考虑高度，主要考虑位置，可以吗？

比如我们把高度从低到高排个序
然后按顺序考虑建筑物
相当于每次考虑当前建筑物，可以直接把之前建筑物给覆盖掉，因为之前考虑的建筑肯定更矮

好像不可行，没有数据结构可以这样操作
如果用数组直接保存每个位置当前的最高点也不行，0 <= lefti < righti <= 2^31 - 1 ，范围太大了

② 那我们如果不考虑位置，主要考虑高度，可以吗？

就是按照建筑物左边位置从左到右依次考虑建筑物，即扫描线从左到右移过去
建筑物右边位置，则通过 pair<右边高度，右边位置> 存储

建筑物右边位置放入一个集合中存储，代表当前还有这些建筑物被扫描线压到
然后考虑最高的一个（矮的会被覆盖）
所以采用优先队列
（其实有些没有被扫描线压到的也被放在了里面，可能没有及时拿出来，到时候直接对比扫描线，如果在扫描线左边，直接抛弃就可以）

然后每次扫描线移动到建筑物左边位置时，对比优先队列中，扫描线压到的最高建筑物
如果优先队列中的那个更高，则这个当前被覆盖了，把它的右边位置，扔到优先队列就没事了
如果当前建筑物的左边更高，则把这个位置当成天际线的一点，并也把它右边位置扔到优先队列里

考虑特殊情况

1. 优先队列中的没有被扫描线压到，抛弃的时候，也可能形成天际线一点
2. 如果多个天际线上点在同一直线上，[0, 2]，[1, 2]，[1, 4]，例 x = 1 时，有 y = 2 和 y = 4，则需要考虑前一个点，x = 0，如果 x = 1 的 y 最大值大于 x = 0 的 y，则取 y 最大值，否则取 y 最小值

代码如下：

class Solution {
public:priority_queue<pair<int, int> > temp_right;vector<vector<int> > res_temp;vector<vector<int> > res;vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {int f = -1;vector<int> t(2);pair<int, int> flag;for(int i = 0; i < buildings.size(); i++) {while(!temp_right.empty()) {flag = temp_right.top();if(flag.second < f) {temp_right.pop();}else if(flag.second < buildings[i][0]) {temp_right.pop();while(!temp_right.empty() && flag.second > temp_right.top().second) {temp_right.pop();}if(!temp_right.empty()) {t[0] = flag.second;t[1] = temp_right.top().first;}else {t[0] = flag.second;t[1] = 0;}res_temp.push_back(t);f = t[0];}else {if(flag.first < buildings[i][2]) {t[0] = buildings[i][0];t[1] = buildings[i][2];res_temp.push_back(t);f = t[0];}break;}}if(temp_right.empty()) {t[0] = buildings[i][0];t[1] = buildings[i][2];res_temp.push_back(t);f = t[0];}temp_right.push(make_pair(buildings[i][2], buildings[i][1]));}while(!temp_right.empty()) {flag = temp_right.top();temp_right.pop();while(!temp_right.empty() && flag.second > temp_right.top().second) {temp_right.pop();}if(f <= flag.second) {if(!temp_right.empty()) {t[0] = flag.second;t[1] = temp_right.top().first;}else {t[0] = flag.second;t[1] = 0;}res_temp.push_back(t);f = t[0];}}int p = res_temp[0][0], p1 = res_temp[0][1], p2 = res_temp[0][1];for(int i = 0; i < res_temp.size(); i++) {if(res_temp[i][0] != p) {if(res.empty()) {t[0] = p;t[1] = p1;res.push_back(t);}else {if(p1 > res[res.size() - 1][1]) {t[0] = p;t[1] = p1;res.push_back(t);}else {t[0] = p;t[1] = p2;res.push_back(t);}}p = res_temp[i][0];p1 = res_temp[i][1];p2 = res_temp[i][1];}else {p1 = max(p1, res_temp[i][1]);p2 = min(p2, res_temp[i][1]);}}if(p1 > res[res.size() - 1][1]) {t[0] = p;t[1] = p1;res.push_back(t);}else {t[0] = p;t[1] = p2;res.push_back(t);}return res;}
};