Leetcode 218 The Skyline Problem
https://leetcode.com/problems/the-skyline-problem/description/题意，给定一个array的vector, （代表从2-9这个区间内我有一个10的大楼），我需要求出这个都会的天际线（描边）
buildings = [,,,,]
output [,,,,,,]
起首第一个思想：
我要描边，什么时候会有这个需求？肯定是我的高度发生改变的时候需要记录下来
非常容易想到扫描线算法，确定event上升沿降落沿，并且用一个数据结构去维护此时的最大值，但是这个数据结构还要有肯定的快速删除的能力，所以用multiset
class Solution {
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
vector<vector<int>> ret;
vector<pair<int, int>> events;
for (auto& b : buildings) {
events.push_back({b, -b});
events.push_back({b, b});
}
sort(events.begin(), events.end());
int prevH = 0;
multiset<int> height;
height.insert(0);
for(auto& : events) {
if (h < 0) {
height.insert(-h);
} else {
height.erase(height.find(h));
}
int currentH = *height.rbegin();
if(currentH != prevH) {
ret.push_back({x,currentH});
prevH = currentH;
}
}
return ret;
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]