218. The Skyline Problem (LeetCode)

天际线问题，参考自: 百草园

天际线为当前线段的最高高度，所以用最大堆处理，当遍历到线段右端点时需要删除该线段的高度，priority_queue不提供删除的操作，要用unordered_map来标记要删除的元素。从heap中pop的时候先看有没有被标记过，如果标记过，就一直pop直到空或都找到没被标记过的值(之前的值被标记过也要删除干净，因为到当前x坐标时，标记过的高度已失效)。为排除冗余答案，需要提前对线段排序，横坐标相等时，都是左端点，按y从大到小(只记录高的端点)，都是右端点，按y从小到大(只记录高的端点)，一左一右，左在前右在后，不重复记录。

 1 class Solution {
 2 private:
 3     enum NODE_TYPE {LEFT, RIGHT};
 4     struct node{
 5         int x,y;
 6         NODE_TYPE type;
 7         node(int _x, int _y, NODE_TYPE _type): x(_x),y(_y),type(_type){}
 8     };
 9     
10 public:
11     vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
12         vector<node> height;
13         for(int i=0;i<buildings.size();i++){
14             height.push_back(node(buildings[i][0],buildings[i][2],LEFT));
15             height.push_back(node(buildings[i][1],buildings[i][2],RIGHT));
16         }
17         sort(height.begin(),height.end(),[](const node &a, const node& b) {
18             if(a.x!=b.x)return a.x<b.x;
19             else if(a.type==b.type && a.type == LEFT) return a.y>b.y;
20             else if(a.type==b.type && a.type == RIGHT) return a.y<b.y;
21             else return a.type == LEFT;
22         });
23         priority_queue<int> heap;
24         heap.push(0);
25         unordered_map<int,int> mp; // remove the element in heap
26         int cur=0,pre=0;
27         vector<vector<int>> res;
28         for(auto & h : height){
29             if(h.type == LEFT){
30                 heap.push(h.y);
31             } else {
32               mp[h.y]++;
33                 while(!heap.empty()&&mp[heap.top()]>0) {
34                     mp[heap.top()]--;
35                     heap.pop();
36                 }
37             }
38             cur = heap.top();
39             if(cur!=pre){
40                 res.push_back({h.x,cur});
41                 pre = cur;
42             }
43         }
44         return res;
45     }
46 };