ToB企服应用市场:ToB评测及商务社交产业平台

标题: Leetcode 218 The Skyline Problem [打印本页]

---

作者: 愛在花開的季節    时间: 2024-10-9 23:28
标题: Leetcode 218 The Skyline Problem
https://leetcode.com/problems/the-skyline-problem/description/
题意，给定一个array的vector, [2,9, 10]（代表从2-9这个区间内我有一个10的大楼），我需要求出这个都会的天际线（描边）
buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
output [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
起首第一个思想：
我要描边，什么时候会有这个需求？肯定是我的高度发生改变的时候需要记录下来
非常容易想到扫描线算法，确定event上升沿降落沿，并且用一个数据结构去维护此时的最大值，但是这个数据结构还要有肯定的快速删除的能力，所以用multiset

1. class Solution {
2. public:
3.     vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
4.         vector<vector<int>> ret;
5.         vector<pair<int, int>> events;
6.         for (auto& b : buildings) {
7.             events.push_back({b[0], -b[2]});
8.             events.push_back({b[1], b[2]});
9.         }
10.         sort(events.begin(), events.end());
11.         int prevH = 0;
12.         multiset<int> height;
13.         height.insert(0);
15.         for(auto& [x,h]: events) {
16.             if (h < 0) {
17.                 height.insert(-h);
18.             } else {
19.                 height.erase(height.find(h));
20.             }
21.             int currentH = *height.rbegin();
22.             if(currentH != prevH) {
23.                 ret.push_back({x,currentH});
24.                 prevH = currentH;
25.             }
26.         }
27.         return ret;
28.     }
29. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4