218. The Skyline Problem

时间：2020-08-05 00:05:28 收藏：0 阅读：62

问题：

给定一个数组，表示楼的宽+高[x1,x2,h]，求所形成的城市轮廓。

技术分享图片

Input
[[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output
[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

Input
[[1,2,1],[1,2,2],[1,2,3]]
Output
[[1,3],[2,0]]

解法：

解法一：FenwickTree

利用特点：通常的FenwickTree（如下图）所求为，前0～i个元素的和。

前面的值贡献构成->后面的值

技术分享图片

这里，我们利用后缀构造，求第i～∞个元素中的最大值。

后面的值(x2) 贡献构成->前面的值(x1~x2之间的值)。

index：x2
value：max(h)

例如，上图中

tree[2]：表示node[2]的最大值和node[3]的最大值，再求最大值。
tree[8]：表示node[8]，node[9]...node[15]的最大值。

在本问题中，我们每读入一个楼的信息（遍历到x1的位置时），[x1,x2,h] 将上述的数据结构 update(x2, h)

更新node[x2]上的值，同时更新<x2的idx上的各个node的值。

当我们求，x0的最大值时，还未录入h，x0累计>x0的各个值。由于刚开始所以都为0
当我们求，x1.5的最大值时，已录入h，x1.5累计>x1.5的各个值，包含x2。因此为h
当我们求，x3的最大值时，x3累计>x3的各个值，不包含x2，因此h不能参与计算。

代码参考：

 1 class FenwickTree {//Suffix sum tree (Normal is Preffix sum tree)
 2 public:
 3     FenwickTree(int n):tree(n+1, 0) {}
 4     void update(int i, int delta) {
 5         i++;
 6         while(i>=1){
 7             tree[i]=max(tree[i], delta);
 8             i -= lowbit(i);
 9         }
10     }
11     int getSuMax(int i) {//max(i~infinite)
12         int maxres = 0;
13         i++;
14         while(i<tree.size()){
15             maxres=max(tree[i], maxres);
16             i += lowbit(i);
17         }
18         return maxres;
19     }
20     
21 private:
22     vector<int> tree;
23     int lowbit(int x) {
24         return x&(-x);
25     }
26 };
27 
28 class Event {
29 public:
30     int x;//坐标x
31     int h;//高度
32     int i;//楼号
33 };
34 
35 class Solution {
36 public:
37     static bool cmp(Event a, Event b){
38         return (a.x == b.x)? a.h > b.h : a.x < b.x;//x坐标相同的情况下，高的排前面（防止二重输出）
39     }
40     vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
41         set<vector<int>> res;
42         vector<Event> eventlist;
43         map<int,int> posX;//映射x2排序后的index
44         int i=0, j=0;
45         for(vector<int> b:buildings){
46             eventlist.push_back({b[0], b[2], j});//楼开始
47             eventlist.push_back({b[1], -b[2], j++});//楼结束
48         }
49         sort(eventlist.begin(), eventlist.end(), cmp);
50         for(int i=0; i<eventlist.size(); i++){
51             posX.insert({eventlist[i].x, i});
52         }
53         FenwickTree ftree(eventlist.size());
54         for(Event e:eventlist){
55             int maxh = ftree.getSuMax(posX[e.x]);//FenwickTree query
56             if(e.h > 0) {
57                 int x2 = buildings[e.i][1];
58                 ftree.update(posX[x2], e.h);//FenwickTree update
59                 if(abs(e.h) > maxh) res.insert({e.x, e.h});
60             } else {
61                 int maxh2 = ftree.getSuMax(posX[e.x]+1);
62                 if(abs(e.h) > maxh2) res.insert({e.x, maxh2});
63             }
64         }
65         vector<vector<int>> res1(res.begin(), res.end());//去重
66         return res1;
67     }
68 };

原文：https://www.cnblogs.com/habibah-chang/p/13435520.html