218. The Skyline Problem.md

218. The Skyline Problem

思路

扫描法

想象一下从左到右扫描，如果当前扫描线穿过的building的最大高度与上一次的最大高度不一样，说明遇到了转折点，记录这个转折点即可。

首先为了从左到右扫描，我们需要将所有边界（包括左边界和右边界）与高度的pair按照水平位置排序（为了区分左右边界，将左边界的高度存为负数，建立左边界和负高度的pair）；

然后，我们还需要用一个容器记录当前扫描线穿过的building的所有高度，而且能够快速获得最大高度以及删除某个高度，那么multiset就很不错。我们先插入高度0为初始高度，然后开始扫描排好序的<边界,高度>pair:

• 如果遇到高度为负值的pair，说明是左边界，那么将高度插入multiset中；
• 否则说明遇到了右边界，即扫描线马上就会离开这个building，应该从multiset中删除这个高度。然后取出此时multiset中最高的高度，判断是否等于上一轮的最大高度，若不是则表示遇到了转折，需要存放到结果数组中。

需要注意的是这里我们使用multiset的erase方法时应该传入的是一个iterator而不是某个高度值，因为后者会删除所有等于该高度值的元素，而正确的应该是一次只删除一个。

扫描过程动图可参考此处

时间复杂度O(nlogn)；空间复杂度O(n)

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