Home LeetCode-218 The Skyline Problem
Post
Cancel

LeetCode-218 The Skyline Problem

Description

example

如图,求上升沿和下降沿转折处的坐标

Constraints

要求时间复杂度\(O(nlogn)\),其中\(n\)为输入的建筑物个数

Solution

每个区间拆成2条纵线,按坐标\(x\)排序。然后用平衡树维护坐标\(y\)

Code

class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        vector<vector<int>> ans;
        vector<pair<int, int>> input;
        for(auto &vec : buildings) {
            input.emplace_back(vec[0], -vec[2]);
            input.emplace_back(vec[1], vec[2]);
        }
        sort(input.begin(), input.end());
        int last {0};
        multiset<int> s {0};
        for(auto &p : input) {
            if(p.second < 0) s.emplace(-p.second);
            else s.erase(s.find(p.second));
            auto mx = *--s.end();
            if(last != mx) {
                vector<int> vp {p.first, mx};
                ans.emplace_back(std::move(vp));
                last = mx;
            }
        }
        return ans;
    }
};

LeetCode-218 The Skyline Problem

This post is licensed under CC BY 4.0 by the author.
Contents