题目描述
城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。
现在,假设您获得了城市风光照片(图A)上显示的所有建筑物的位置和高度,请编写一个程序以输出由这些建筑物形成的天际线(图B)。
每个建筑物的几何信息用三元组 [Li,Ri,Hi]
表示,其中 Li
和 Ri
分别是第 i
座建筑物左右边缘的 x
坐标,Hi
是其高度。可以保证 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX
和 Ri - Li > 0
。您可以假设所有建筑物都是在绝对平坦且高度为 0
的表面上的完美矩形。
例如,图A中所有建筑物的尺寸记录为:[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ]
。
输出是以 [ [x1,y1], [x2, y2], [x3, y3], ... ]
格式的“关键点”(图B中的红点)的列表,它们唯一地定义了天际线。关键点是水平线段的左端点。请注意,最右侧建筑物的最后一个关键点仅用于标记天际线的终点,并始终为零高度。此外,任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。
例如,图B中的天际线应该表示为:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]
。
说明
- 任何输入列表中的建筑物数量保证在
[0, 10000]
范围内。 - 输入列表已经按左
x
坐标Li
进行升序排列。 - 输出列表必须按
x
位排序。 - 输出天际线中不得有连续的相同高度的水平线。例如
[...[2 3], [4 5], [7 5], [11 5], [12 7]...]
是不正确的答案;三条高度为 5 的线应该在最终输出中合并为一个:[...[2 3], [4 5], [12 7], ...]
样例
输入:[[2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8]]
输出:[[2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0]]
算法
(扫描线,多重集) $O(n \log n)$
- 将每个建筑看成在 x 轴两个竖线,一条表示开始,一条表示结束。
- 在 x 轴上应用扫描线,扫描各个竖线,用
multiset
记录当前竖线的最大高度。 - 如果当前位置上的最大高度和上次的不一致,则加入答案。
时间复杂度
- 扫描线共有 $O(n)$ 个位置,每个位置需要 $O(\log n)$ 的时间维护。
- 故总时间复杂度为 $O(n \log n)$。
空间复杂度
- 多重集和答案都需要 $O(n)$ 的空间。
C++ 代码
struct Tuple {
int x, y, d;
Tuple(int x_, int y_, int d_): x(x_), y(y_), d(d_) {}
bool operator < (const Tuple& other) const {
return x < other.x;
}
};
class Solution {
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
int n = buildings.size();
vector<Tuple> line;
for (int i = 0; i < n; i++) {
line.emplace_back(buildings[i][0], buildings[i][2], 1);
line.emplace_back(buildings[i][1], buildings[i][2], -1);
}
sort(line.begin(), line.end());
vector<vector<int>> ans;
multiset<int> heights;
heights.insert(0);
int last = -1;
for (int i = 0; i < 2 * n; i++) {
while (1) {
if (line[i].d == 1)
heights.insert(line[i].y);
else
heights.erase(heights.find(line[i].y));
if (i == 2 * n - 1 || line[i].x != line[i + 1].x)
break;
i++;
}
int cur = *heights.crbegin();
if (cur != last) {
ans.push_back({line[i].x, cur});
last = cur;
}
}
return ans;
}
};
按照大佬的思路我改造了下代码,不知是否正确,leetcode上是ac了的。。
大佬🐂🍺,面试遇到这题我等只有等死了hhh, 话说 y总后面的课会讲到 扫描线这个内容吗?感觉这道题和LeetCode 352. Data Stream as Disjoint Intervals 有些类似,多了一维高度所以不能直接用map\<int, int>