題目來(lái)源
輪廓線問(wèn)題顶猜，具體解釋見這里，解釋的特別詳細(xì)痘括。
然后實(shí)際上要注意的是每個(gè)建筑的頂上兩點(diǎn)长窄，然后注意用負(fù)值區(qū)分是左端點(diǎn)還是右端點(diǎn)，并且左端點(diǎn)為負(fù)纲菌，因?yàn)楫?dāng)遍歷到某個(gè)x值挠日，有一個(gè)矩形的右端點(diǎn)及另一個(gè)的左端點(diǎn)，這時(shí)候需要先考慮左端點(diǎn)翰舌。然后所有的端點(diǎn)按照x值大小排序嚣潜，當(dāng)遍歷到某點(diǎn)的時(shí)候，會(huì)影響這個(gè)點(diǎn)的只有某部分椅贱，所以不用考慮所有點(diǎn)懂算。
代碼如下：
class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
vector<pair<int, int>> res;
multiset<pair<int, int>> seq;
pair<int, int> cur{0, 0};
for (auto point : buildings) {
seq.emplace(make_pair(point[0], -point[2]));
seq.emplace(make_pair(point[1], point[2]));
}
multiset<int> heights{0};
for (auto point : seq) {
if (point.second < 0)
heights.emplace(-point.second);
else
heights.erase(heights.find(point.second));
if (*heights.rbegin() != cur.second) {
cur.first = point.first;
cur.second = *heights.rbegin();
res.push_back(cur);
}
}
return res;
}
};
