218. 天际线问题
题目描述
从远处看一座城市，所有建筑合在一起形成的外轮廓就是天际线。输入数组 buildings，第 i 座建筑记为 buildings[i]，它是三元组 [lefti,righti,heighti]：左边缘横坐标为 lefti，右边缘横坐标为 righti，高度为 heighti。
每座建筑都是立在高度为 0 的平地上的长方形。两座建筑之间空着的地面也算作天际线的一部分。
用关键点列表 [[x1,y1],[x2,y2],...] 表示天际线，按 x 升序排列。每个关键点是一段水平线的左端点，表示从横坐标 x 开始轮廓高度变为 y。最后一个关键点位于最右侧建筑的右端，其 y 为 0，用来标明天际线结束。
相邻的两个关键点高度不能相同。例如 [...,[2,3],[4,5],[7,5],[11,5],[12,7],...] 不合法，三段高度为 5 的线要合成一段，写成 [...,[2,3],[4,5],[12,7],...]。
示例 1
输入：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]]
解释：x = 2 时轮廓升到 10，x = 3 升到 15，x = 7 降到 12，x = 12 落到地面；之后在 15、20 处变为 10、8，x = 24 回到 0。
示例 2
输入：buildings = [[0,2,3],[2,5,3]] 输出：[[0,3],[5,0]]
解释：两座建筑同高且相接，合并成一段高度为 3 的轮廓，从 0 延伸到 5。
数据范围
1 <= buildings.length <= 10^40 <= lefti < righti <= 2^31 - 11 <= heighti <= 2^31 - 1buildings按lefti非递减排列。
解题思路：扫描线 + 优先队列（延迟删除）
轮廓高度只可能在某栋建筑的左边或右边发生变化，所以把每栋楼拆成“左端点进入”和“右端点离开”两个事件，按 x 从左到右扫描。用最大堆（存 (-h, r)）维护当前覆盖扫描线的建筑，堆顶就是此刻的轮廓高度。处理事件时先把右端点 r <= x 的过期楼从堆顶弹掉（延迟删除），再把新楼压入堆，最后若堆顶高度与上一个关键点高度不同，就记录关键点 [x, 堆顶高度]。
为什么正确
处理完坐标 x 上的事件后，堆顶的高度等于 x 右侧紧邻处所有覆盖建筑的最大高度；堆里可以残留已过期的楼，但它们只要不在堆顶就不影响答案。
复杂度分析
时间 O(n log n)（排序与堆操作），空间 O(n)。
易错点
同一 x 上既有楼结束又有楼开始时，必须先处理完该 x 的所有事件再看高度，否则会产生 [x,0] 紧跟 [x,h] 的多余关键点；排序时把开始事件（-h 为负）排在结束事件（0）前面、高楼排在矮楼前面，就能自然避免。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
events = []
for l, r, h in buildings:
events.append((l, -h, r))
events.append((r, 0, 0))
events.sort()
res = [[0, 0]]
heap = [(0, float('inf'))]
for x, negH, r in events:
while heap[0][1] <= x:
heapq.heappop(heap)
if negH:
heapq.heappush(heap, (negH, r))
if res[-1][1] != -heap[0][0]:
res.append([x, -heap[0][0]])
return res[1:]class Solution {
public List<List<Integer>> getSkyline(int[][] buildings) {
List<long[]> events = new ArrayList<>();
for (int[] b : buildings) {
events.add(new long[]{b[0], -(long) b[2], b[1]});
events.add(new long[]{b[1], 0, 0});
}
events.sort((p, q) -> {
if (p[0] != q[0]) {
return Long.compare(p[0], q[0]);
}
if (p[1] != q[1]) {
return Long.compare(p[1], q[1]);
}
return Long.compare(p[2], q[2]);
});
List<List<Integer>> res = new ArrayList<>();
res.add(Arrays.asList(0, 0));
PriorityQueue<long[]> heap = new PriorityQueue<>((p, q) -> {
return Long.compare(p[0], q[0]);
});
heap.add(new long[]{0, Long.MAX_VALUE});
for (long[] e : events) {
long x = e[0], negH = e[1], r = e[2];
while (heap.peek()[1] <= x) {
heap.poll();
}
if (negH != 0) {
heap.add(new long[]{negH, r});
}
if (res.get(res.size() - 1).get(1) != -heap.peek()[0]) {
res.add(Arrays.asList((int) x, (int) (-heap.peek()[0])));
}
}
return res.subList(1, res.size());
}
}class Solution {
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
vector<array<long long, 3>> events;
for (auto& b : buildings) {
events.push_back({b[0], -(long long)b[2], b[1]});
events.push_back({b[1], 0, 0});
}
sort(events.begin(), events.end());
vector<vector<int>> res = {{0, 0}};
priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<>> heap;
heap.push({0, LLONG_MAX});
for (auto& e : events) {
long long x = e[0], negH = e[1], r = e[2];
while (heap.top().second <= x) {
heap.pop();
}
if (negH) {
heap.push({negH, r});
}
if (res.back()[1] != -heap.top().first) {
res.push_back({(int)x, (int)(-heap.top().first)});
}
}
res.erase(res.begin());
return res;
}
};type skyHeap [][2]int
func (h skyHeap) Len() int { return len(h) }
func (h skyHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h skyHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *skyHeap) Push(v any) { *h = append(*h, v.([2]int)) }
func (h *skyHeap) Pop() any {
old := *h
v := old[len(old)-1]
*h = old[:len(old)-1]
return v
}
func getSkyline(buildings [][]int) [][]int {
events := [][3]int{}
for _, b := range buildings {
events = append(events, [3]int{b[0], -b[2], b[1]})
events = append(events, [3]int{b[1], 0, 0})
}
sort.Slice(events, func(i, j int) bool {
p, q := events[i], events[j]
if p[0] != q[0] {
return p[0] < q[0]
}
if p[1] != q[1] {
return p[1] < q[1]
}
return p[2] < q[2]
})
res := [][]int{{0, 0}}
h := &skyHeap{{0, math.MaxInt64}}
for _, e := range events {
x, negH, r := e[0], e[1], e[2]
for (*h)[0][1] <= x {
heap.Pop(h)
}
if negH != 0 {
heap.Push(h, [2]int{negH, r})
}
if res[len(res)-1][1] != -(*h)[0][0] {
res = append(res, []int{x, -(*h)[0][0]})
}
}
return res[1:]
}const heappush = (h, e) => {
h.push(e);
for (let i = h.length - 1, p; i > 0 && h[p = (i - 1) >> 1][0] > h[i][0]; i = p) [h[p], h[i]] = [h[i], h[p]];
};
const heappop = h => {
const top = h[0], last = h.pop();
if (h.length) {
h[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1; let s = i;
if (l < h.length && h[l][0] < h[s][0]) s = l;
if (r < h.length && h[r][0] < h[s][0]) s = r;
if (s === i) break;
[h[s], h[i]] = [h[i], h[s]]; i = s;
}
}
return top;
};
var getSkyline = function(buildings) {
const events = [];
for (const [l, r, h] of buildings) {
events.push([l, -h, r]);
events.push([r, 0, 0]);
}
events.sort((p, q) => p[0] - q[0] || p[1] - q[1] || p[2] - q[2]);
const res = [[0, 0]];
const heap = [[0, Infinity]];
for (const [x, negH, r] of events) {
while (heap[0][1] <= x) {
heappop(heap);
}
if (negH) {
heappush(heap, [negH, r]);
}
if (res[res.length - 1][1] !== -heap[0][0]) {
res.push([x, -heap[0][0]]);
}
}
return res.slice(1);
};const heappush = (h: number[][], e: number[]) => {
h.push(e);
for (let i = h.length - 1, p; i > 0 && h[p = (i - 1) >> 1][0] > h[i][0]; i = p) [h[p], h[i]] = [h[i], h[p]];
};
const heappop = (h: number[][]) => {
const top = h[0], last = h.pop()!;
if (h.length) {
h[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1; let s = i;
if (l < h.length && h[l][0] < h[s][0]) s = l;
if (r < h.length && h[r][0] < h[s][0]) s = r;
if (s === i) break;
[h[s], h[i]] = [h[i], h[s]]; i = s;
}
}
return top;
};
function getSkyline(buildings: number[][]): number[][] {
const events: number[][] = [];
for (const [l, r, h] of buildings) {
events.push([l, -h, r]);
events.push([r, 0, 0]);
}
events.sort((p, q) => p[0] - q[0] || p[1] - q[1] || p[2] - q[2]);
const res: number[][] = [[0, 0]];
const heap: number[][] = [[0, Infinity]];
for (const [x, negH, r] of events) {
while (heap[0][1] <= x) {
heappop(heap);
}
if (negH) {
heappush(heap, [negH, r]);
}
if (res[res.length - 1][1] !== -heap[0][0]) {
res.push([x, -heap[0][0]]);
}
}
return res.slice(1);
}其他解法
扫描线从左到右处理所有左右边界，用堆维护当前最高的建筑；分治把问题拆成两个子问题，合并时只需要取两条天际线的较高者。两者都是 O(n log n)。
解法 2：分治（合并天际线） 时间 O(n log n)，空间 O(n)
把建筑分成左右两半，分别递归求出天际线，再合并。只有一栋建筑 [l, r, h] 时，天际线就是 [[l, h], [r, 0]]。合并两条天际线时像归并排序一样用两个指针按 x 从小到大处理关键点，分别记录两条线当前的高度 h1、h2；每处理一个 x（两边 x 相同就一起处理），合并后的高度就是 max(h1, h2)；只有高度和上一个关键点不同时才输出新的关键点。
不需要堆和事件排序，合并过程和归并排序完全对应，也容易证明正确。需要递归和频繁创建临时数组，合并时 x 相等、高度去重等细节需要小心。
from typing import List
class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
def merge(a, b):
res = []
i = j = h1 = h2 = 0
def add(x, h):
if not res or res[-1][1] != h:
res.append([x, h])
while i < len(a) and j < len(b):
if a[i][0] < b[j][0]:
x, h1 = a[i]
i += 1
elif a[i][0] > b[j][0]:
x, h2 = b[j]
j += 1
else:
x, h1 = a[i]
h2 = b[j][1]
i += 1
j += 1
add(x, max(h1, h2))
for x, h in a[i:] + b[j:]:
add(x, h)
return res
def solve(lo, hi):
if lo == hi:
l, r, h = buildings[lo]
return [[l, h], [r, 0]]
mid = (lo + hi) // 2
return merge(solve(lo, mid), solve(mid + 1, hi))
return solve(0, len(buildings) - 1)class Solution {
private static void add(List<List<Integer>> res, int x, int h) {
if (res.isEmpty() || res.get(res.size() - 1).get(1) != h) res.add(Arrays.asList(x, h));
}
private List<List<Integer>> merge(List<List<Integer>> a, List<List<Integer>> b) {
List<List<Integer>> res = new ArrayList<>();
int i = 0, j = 0, h1 = 0, h2 = 0;
while (i < a.size() && j < b.size()) {
int xa = a.get(i).get(0), xb = b.get(j).get(0), x;
if (xa < xb) {
x = xa; h1 = a.get(i).get(1); i++;
} else if (xa > xb) {
x = xb; h2 = b.get(j).get(1); j++;
} else {
x = xa; h1 = a.get(i).get(1); h2 = b.get(j).get(1); i++; j++;
}
add(res, x, Math.max(h1, h2));
}
for (; i < a.size(); i++) add(res, a.get(i).get(0), a.get(i).get(1));
for (; j < b.size(); j++) add(res, b.get(j).get(0), b.get(j).get(1));
return res;
}
private List<List<Integer>> solve(int[][] bs, int lo, int hi) {
if (lo == hi) {
List<List<Integer>> res = new ArrayList<>();
res.add(Arrays.asList(bs[lo][0], bs[lo][2]));
res.add(Arrays.asList(bs[lo][1], 0));
return res;
}
int mid = (lo + hi) / 2;
return merge(solve(bs, lo, mid), solve(bs, mid + 1, hi));
}
public List<List<Integer>> getSkyline(int[][] buildings) {
return solve(buildings, 0, buildings.length - 1);
}
}class Solution {
using Line = vector<vector<int>>;
static void add(Line& res, int x, int h) {
if (res.empty() || res.back()[1] != h) res.push_back({x, h});
}
Line merge(const Line& a, const Line& b) {
Line res;
size_t i = 0, j = 0;
int h1 = 0, h2 = 0;
while (i < a.size() && j < b.size()) {
int x;
if (a[i][0] < b[j][0]) {
x = a[i][0]; h1 = a[i][1]; i++;
} else if (a[i][0] > b[j][0]) {
x = b[j][0]; h2 = b[j][1]; j++;
} else {
x = a[i][0]; h1 = a[i][1]; h2 = b[j][1]; i++; j++;
}
add(res, x, max(h1, h2));
}
for (; i < a.size(); i++) add(res, a[i][0], a[i][1]);
for (; j < b.size(); j++) add(res, b[j][0], b[j][1]);
return res;
}
Line solve(const vector<vector<int>>& bs, int lo, int hi) {
if (lo == hi) return {{bs[lo][0], bs[lo][2]}, {bs[lo][1], 0}};
int mid = (lo + hi) / 2;
return merge(solve(bs, lo, mid), solve(bs, mid + 1, hi));
}
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
return solve(buildings, 0, buildings.size() - 1);
}
};func getSkyline(buildings [][]int) [][]int {
add := func(res [][]int, x, h int) [][]int {
if len(res) == 0 || res[len(res)-1][1] != h {
res = append(res, []int{x, h})
}
return res
}
merge := func(a, b [][]int) [][]int {
res := [][]int{}
i, j, h1, h2 := 0, 0, 0, 0
for i < len(a) && j < len(b) {
var x int
if a[i][0] < b[j][0] {
x, h1 = a[i][0], a[i][1]
i++
} else if a[i][0] > b[j][0] {
x, h2 = b[j][0], b[j][1]
j++
} else {
x, h1, h2 = a[i][0], a[i][1], b[j][1]
i++
j++
}
res = add(res, x, max(h1, h2))
}
for ; i < len(a); i++ {
res = add(res, a[i][0], a[i][1])
}
for ; j < len(b); j++ {
res = add(res, b[j][0], b[j][1])
}
return res
}
var solve func(lo, hi int) [][]int
solve = func(lo, hi int) [][]int {
if lo == hi {
b := buildings[lo]
return [][]int{{b[0], b[2]}, {b[1], 0}}
}
mid := (lo + hi) / 2
return merge(solve(lo, mid), solve(mid+1, hi))
}
return solve(0, len(buildings)-1)
}var getSkyline = function(buildings) {
const add = (res, x, h) => {
if (res.length === 0 || res[res.length - 1][1] !== h) res.push([x, h]);
};
const merge = (a, b) => {
const res = [];
let i = 0, j = 0, h1 = 0, h2 = 0;
while (i < a.length && j < b.length) {
let x;
if (a[i][0] < b[j][0]) {
x = a[i][0]; h1 = a[i][1]; i++;
} else if (a[i][0] > b[j][0]) {
x = b[j][0]; h2 = b[j][1]; j++;
} else {
x = a[i][0]; h1 = a[i][1]; h2 = b[j][1]; i++; j++;
}
add(res, x, Math.max(h1, h2));
}
for (; i < a.length; i++) add(res, a[i][0], a[i][1]);
for (; j < b.length; j++) add(res, b[j][0], b[j][1]);
return res;
};
const solve = (lo, hi) => {
if (lo === hi) {
const [l, r, h] = buildings[lo];
return [[l, h], [r, 0]];
}
const mid = (lo + hi) >> 1;
return merge(solve(lo, mid), solve(mid + 1, hi));
};
return solve(0, buildings.length - 1);
};function getSkyline(buildings: number[][]): number[][] {
const add = (res: number[][], x: number, h: number): void => {
if (res.length === 0 || res[res.length - 1][1] !== h) res.push([x, h]);
};
const merge = (a: number[][], b: number[][]): number[][] => {
const res: number[][] = [];
let i = 0, j = 0, h1 = 0, h2 = 0;
while (i < a.length && j < b.length) {
let x: number;
if (a[i][0] < b[j][0]) {
x = a[i][0]; h1 = a[i][1]; i++;
} else if (a[i][0] > b[j][0]) {
x = b[j][0]; h2 = b[j][1]; j++;
} else {
x = a[i][0]; h1 = a[i][1]; h2 = b[j][1]; i++; j++;
}
add(res, x, Math.max(h1, h2));
}
for (; i < a.length; i++) add(res, a[i][0], a[i][1]);
for (; j < b.length; j++) add(res, b[j][0], b[j][1]);
return res;
};
const solve = (lo: number, hi: number): number[][] => {
if (lo === hi) {
const [l, r, h] = buildings[lo];
return [[l, h], [r, 0]];
}
const mid = (lo + hi) >> 1;
return merge(solve(lo, mid), solve(mid + 1, hi));
};
return solve(0, buildings.length - 1);
};