218. The Skyline Problem (LeetCode)

天際線問題，參考自: 百草園

天際線為當(dāng)前線段的最高高度，所以用最大堆處理，當(dāng)遍歷到線段右端點時需要刪除該線段的高度，priority_queue不提供刪除的操作，要用unordered_map來標(biāo)記要刪除的元素。從heap中pop的時候先看有沒有被標(biāo)記過，如果標(biāo)記過，就一直pop直到空或都找到?jīng)]被標(biāo)記過的值(之前的值被標(biāo)記過也要刪除干凈，因為到當(dāng)前x坐標(biāo)時，標(biāo)記過的高度已失效)。為排除冗余答案，需要提前對線段排序，橫坐標(biāo)相等時，都是左端點，按y從大到小(只記錄高的端點)，都是右端點，按y從小到大(只記錄高的端點)，一左一右，左在前右在后，不重復(fù)記錄。

 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 };

posted @ 2019-07-13 20:18 demianzhang 閱讀(269) 評論(0) 收藏舉報

刷新頁面返回頂部

Forrest

218. The Skyline Problem (LeetCode)

公告