Leetcode 218. The Skyline Problem 线段树
Leetcode 218. The Skyline Problem 线段树
A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).
The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.
For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .
The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.
For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].
Notes:
- The number of buildings in any input list is guaranteed to be in the range
[0, 10000]. - The input list is already sorted in ascending order by the left x position
Li. - The output list must be sorted by the x position.
- There must be no consecutive horizontal lines of equal height in the output skyline. For instance,
[...[2 3], [4 5], [7 5], [11 5], [12 7]...]is not acceptable; the three lines of height 5 should be merged into one in the final output as such:[...[2 3], [4 5], [12 7], ...]
给出一些矩形，求出这些矩形构成的轮廓线，返回轮廓线上每条水平线左边点的坐标集合。
标准的线段树题，而且是带懒惰标记的。
因为坐标可能很大，但是数量却不多，所以首先做离散化处理，将矩形的两个x坐标全部放在一起排序，用map按排序结果编号并记录对应关系。
然后将房子一个个插入树中，因为不要房子右边的点，而且有的房子右边的点可能和其它更低的房子相交，所以右边坐标-1再插入。
高度h作为懒惰标记，当访问到h大于0节点并且要继续向下访问的时候需要向子树更新。
最后逐个节点查询高度值。复杂度O（n*logn），解释见注释。
class node
{
public:
int l, r, h;
};
class Solution {
public:
node tree[20005 << 2];
unordered_map<int, int> mp, mp2;
void build(int l, int r,int now)
{
tree[now].l = l;
tree[now].r = r;
tree[now].h = 0;
if(l == r) return ;
int mid = (l + r) >> 1;
build(l, mid, now << 1);
build(mid + 1, r, now << 1 | 1);
}
void insert(int l, int r, int h, int now)
{
if(tree[now].h >= h) return ;//无需更新
if(tree[now].l == l && tree[now].r == r)
{
tree[now].h = h;
//cout<<tree[now].l<<" "<<tree[now].r<<" "<<tree[now].h<<endl;
return ;
}
if(tree[now].h > 0)//懒惰标记
{
tree[now << 1].h = max(tree[now].h, tree[now << 1].h);
tree[now << 1 | 1].h = max(tree[now].h, tree[now << 1 | 1].h);
tree[now].h = 0;
}
int mid = (tree[now].l + tree[now].r) >> 1;
if(r <= mid) insert(l, r, h, now << 1);
else if(l > mid) insert(l, r, h, now << 1 | 1);
else
{
insert(l, mid, h, now << 1);
insert(mid + 1, r, h, now << 1 | 1);
}
}
void query(vector<pair<int, int>> &res, int now)
{
if(tree[now].l == tree[now].r)
{
if(!res.empty() && tree[now].h == res[res.size() - 1].second) return ;//出去相同高度的相邻点
pair<int, int> tmp = make_pair(mp2[tree[now].l], tree[now].h);
res.push_back(tmp);
return ;
}
if(tree[now].h > 0)//懒惰标记
{
tree[now << 1].h = max(tree[now].h, tree[now << 1].h);
tree[now << 1 | 1].h = max(tree[now].h, tree[now << 1 | 1].h);
tree[now].h = 0;
}
query(res, now << 1);
query(res, now << 1 | 1);
}
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
vector<int> index;
vector<pair<int, int>> res;
if(buildings.empty()) return res;//防止空集导致的越界
for(int i = 0; i < buildings.size(); i++)
for(int j = 0; j < 2; j++)
if(!mp[buildings[i][j]])
{
mp[buildings[i][j]] = 1;
index.push_back(buildings[i][j]);
}
sort(index.begin(), index.end());
int n = index.size();
for(int i = 0; i < n; i++) //离散化，编号-》坐标，坐标-》编号
{
mp[index[i]] = i + 1;
mp2[i + 1] = index[i];
}
build(1, n + 1, 1);//建树
for(int i = 0; i < buildings.size(); i++) insert(mp[buildings[i][0]], mp[buildings[i][1]] - 1, buildings[i][2], 1);//插入房子，线段右边的点不记录，所以右边-1
query(res, 1);
return res;
}
};