mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
54 lines
2.6 KiB
Markdown
54 lines
2.6 KiB
Markdown
# [218. The Skyline Problem](https://leetcode.com/problems/the-skyline-problem/)
|
||
|
||
# 思路
|
||
|
||
**扫描法**
|
||
|
||
想象一下从左到右扫描，如果当前扫描线穿过的building的最大高度与上一次的最大高度不一样，说明遇到了转折点，记录这个转折点即可。
|
||
|
||
首先为了从左到右扫描，我们需要将所有边界（包括左边界和右边界）与高度的pair按照水平位置排序（为了区分左右边界，将左边界的高度存为负数，建立左边界和负高度的pair）；
|
||
|
||
然后，我们还需要用一个容器记录当前扫描线穿过的building的所有高度，而且能够快速获得最大高度以及删除某个高度，那么`multiset`就很不错。我们先插入高度0为初始高度，然后开始扫描排好序的<边界,高度>pair:
|
||
* 如果遇到高度为负值的pair，说明是左边界，那么将高度插入multiset中；
|
||
* 否则说明遇到了右边界，即扫描线马上就会离开这个building，应该从multiset中删除这个高度。然后取出此时multiset中最高的高度，判断是否等于上一轮的最大高度，若不是则表示遇到了转折，需要存放到结果数组中。
|
||
|
||
> 需要注意的是这里我们使用`multiset`的`erase`方法时应该传入的是一个`iterator`而不是某个高度值，因为后者会删除所有等于该高度值的元素，而正确的应该是一次只删除一个。
|
||
|
||
扫描过程动图可参考[此处](https://leetcode-cn.com/problems/the-skyline-problem/solution/218tian-ji-xian-wen-ti-sao-miao-xian-fa-by-ivan_al/)
|
||
|
||
时间复杂度O(nlogn)；空间复杂度O(n)
|
||
|
||
# C++
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
|
||
vector<pair<int,int>>all;
|
||
vector<vector<int>>res;
|
||
multiset<int>st;
|
||
|
||
for(auto &b: buildings){
|
||
all.push_back({b[0], -b[2]}); // 左边界, -高度
|
||
all.push_back({b[1], b[2]}); // 右边界, 高度
|
||
}
|
||
sort(all.begin(), all.end()); // 将边界排好序
|
||
|
||
int pre_h = 0, cur_h;
|
||
st.insert(0);
|
||
for(auto &b: all){ // 从左至右扫描
|
||
if(b.second < 0) st.insert(-b.second);
|
||
else st.erase(st.find(b.second)); // 保证只删除一个
|
||
// else st.erase(b.second); // 这会删除所有b.second, 错误
|
||
|
||
cur_h = *st.rbegin(); // 当前最高高度
|
||
if(cur_h != pre_h){
|
||
res.push_back({b.first, cur_h});
|
||
pre_h = cur_h;
|
||
}
|
||
}
|
||
return res;
|
||
}
|
||
};
|
||
```
|
||
|