218. The Skyline Problem
一個城市的天際線是從遠處觀看時由該城市所有建築物形成的輪廓。給定所有建築物的位置和高度，返回這些建築物共同形成的天際線。
每個建築物的幾何信息在數組 buildings 中給出，其中 buildings[i] = [lefti, righti, heighti]:
- lefti 是第 i 個建築物左邊緣的 x 坐標。
- righti 是第 i 個建築物右邊緣的 x 坐標。
- heighti 是第 i 個建築物的高度。
你可以假設所有的建築物都是完美的矩形，底部在高度 0 的絕對平坦的表面上。
天際線應該表示為按 x 坐標排序的“關鍵點”列表，形式為 [[x1,y1],[x2,y2],...]。每個關鍵點是天際線中某個水平線段的左端點，列表中的最後一個點總是有 y 坐標 0，用於標記天際線在最右邊的建築物結束的地方。在最左邊和最右邊的建築物之間的任何地面應該是天際線輪廓的一部分。
注意：輸出天際線中不能有連續的高度相同的水平線。例如，[..., [2, 3], [4, 5], [7, 5], [11, 5], [12, 7], ...] 是不可接受的；高度為 5 的三條線應合併為一條，最終輸出應為：[..., [2, 3], [4, 5], [12, 7], ...]。
範例：
輸入：buildings = [[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]] 解釋： 圖 A 顯示了輸入的建築物。 圖 B 顯示了由這些建築物形成的天際線。圖 B 中的紅點表示輸出列表中的關鍵點。
Python
from typing import List
import heapq
class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
# Step 1: Create an event list
events = []
for left, right, height in buildings:
events.append((left, -height, right))
events.append((right, 0, 0))
# Step 2: Sort events by position x
events.sort()
# Step 3: Use a max heap to keep track of the tallest building at the current position
result = [[0, 0]]
heap = [(0, float('inf'))] # (height, end)
for x, negH, R in events:
while x >= heap[0][1]: # remove the past buildings
heapq.heappop(heap)
if negH != 0:
heapq.heappush(heap, (negH, R))
if result[-1][1] != -heap[0][0]:
result.append([x, -heap[0][0]])
return result[1:]
C++
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
vector<pair<int, int>> events;
vector<vector<int>> result;
// Step 1: Create an event list
for (const auto& building : buildings) {
events.emplace_back(building[0], -building[2]); // left edge
events.emplace_back(building[1], building[2]); // right edge
}
// Step 2: Sort events by position x
sort(events.begin(), events.end());
// Step 3: Use a max heap to keep track of the tallest building at the current position
multiset<int> heights = {0}; // initialize with ground level height
int prevMaxHeight = 0;
for (const auto& event : events) {
int x = event.first;
int h = event.second;
if (h < 0) {
// It's a left edge, add the height
heights.insert(-h);
} else {
// It's a right edge, remove the height
heights.erase(heights.find(h));
}
// Get the current maximum height
int currentMaxHeight = *heights.rbegin();
// If the current maximum height has changed, add a new key point to the result
if (currentMaxHeight != prevMaxHeight) {
result.push_back({x, currentMaxHeight});
prevMaxHeight = currentMaxHeight;
}
}
return result;
}
};
18.66MB, 22ms
Javascript
/**
* @param {number[][]} buildings
* @return {number[][]}
*/
var getSkyline = function(buildings) {
// Step 1: Create an event list
const events = [];
for (const [left, right, height] of buildings) {
events.push([left, -height]); // start of the building
events.push([right, height]); // end of the building
}
// Step 2: Sort events by position x. If x is the same, use height.
events.sort((a, b) => {
if (a[0] !== b[0]) {
return a[0] - b[0];
}
return a[1] - b[1];
});
// Step 3: Use a max heap to keep track of the tallest building at the current position
const result = [];
const heights = [0]; // Initialize with ground level height
let prevMaxHeight = 0;
for (const [x, h] of events) {
if (h < 0) {
// It's a left edge, add the height
heights.push(-h);
} else {
// It's a right edge, remove the height
const index = heights.indexOf(h);
if (index > -1) {
heights.splice(index, 1);
}
}
// Get the current maximum height
const currentMaxHeight = Math.max(...heights);
// If the current maximum height has changed, add a new key point to the result
if (currentMaxHeight !== prevMaxHeight) {
result.push([x, currentMaxHeight]);
prevMaxHeight = currentMaxHeight;
}
}
return result;
};
62.78MB, 388ms
