LeetCode 题解工作台
天际线问题
城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回 由这些建筑物形成的 天际线 。 每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示： left …
7
题型
4
代码语言
3
相关题
当前训练重点
困难 · 堆
答案摘要
记录下所有建筑物的左右边界线，升序排序之后得到序列 lines。对于每一个边界线 lines[i]，找出所有包含 lines[i] 的建筑物，并确保建筑物的左边界小于等于 lines[i]，右边界大于 lines[i]，则这些建筑物中高度最高的建筑物的高度就是该线轮廓点的高度。可以使用建筑物的高度构建优先队列（大根堆），同时需要注意高度相同的轮廓点需要合并为一个。 from queue impor…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 堆 题型思路
题目描述
城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回 由这些建筑物形成的 天际线 。
每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示：
lefti是第i座建筑物左边缘的x坐标。righti是第i座建筑物右边缘的x坐标。heighti是第i座建筑物的高度。
你可以假设所有的建筑都是完美的长方形，在高度为 0 的绝对平坦的表面上。
天际线 应该表示为由 “关键点” 组成的列表，格式 [[x1,y1],[x2,y2],...] ，并按 x 坐标 进行 排序 。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，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]] 解释： 图 A 显示输入的所有建筑物的位置和高度， 图 B 显示由这些建筑物形成的天际线。图 B 中的红点表示输出列表中的关键点。
示例 2：
输入：buildings = [[0,2,3],[2,5,3]] 输出：[[0,3],[5,0]]
提示：
1 <= buildings.length <= 1040 <= lefti < righti <= 231 - 11 <= heighti <= 231 - 1buildings按lefti非递减排序
解题思路
方法一：扫描线+优先队列
记录下所有建筑物的左右边界线，升序排序之后得到序列 lines。对于每一个边界线 lines[i]，找出所有包含 lines[i] 的建筑物，并确保建筑物的左边界小于等于 lines[i]，右边界大于 lines[i]，则这些建筑物中高度最高的建筑物的高度就是该线轮廓点的高度。可以使用建筑物的高度构建优先队列（大根堆），同时需要注意高度相同的轮廓点需要合并为一个。
from queue import PriorityQueue
class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
skys, lines, pq = [], [], PriorityQueue()
for build in buildings:
lines.extend([build[0], build[1]])
lines.sort()
city, n = 0, len(buildings)
for line in lines:
while city < n and buildings[city][0] <= line:
pq.put([-buildings[city][2], buildings[city][0], buildings[city][1]])
city += 1
while not pq.empty() and pq.queue[0][2] <= line:
pq.get()
high = 0
if not pq.empty():
high = -pq.queue[0][0]
if len(skys) > 0 and skys[-1][1] == high:
continue
skys.append([line, high])
return skys
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n log n) with divide-and-conquer merges; using heaps or segment trees may introduce O(n log n) overhead for insertions and deletions. Space complexity is O(n) for storing intermediate skylines or active heights. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect candidates to identify divide-and-conquer as the core pattern.
- question_mark
Watch for incorrect merges when skylines overlap, which often signals misunderstanding of height transitions.
- question_mark
Candidates who directly sweep with a heap should explain why it preserves correct key points.
常见陷阱
外企场景- error
Failing to correctly handle consecutive buildings with the same height, causing redundant points.
- error
Merging skylines without considering the maximum height at overlapping intervals.
- error
Using naive O(n^2) comparisons instead of divide-and-conquer or heap optimization, leading to timeouts.
进阶变体
外企场景- arrow_right_alt
Compute skylines when buildings are represented as arbitrary polygons instead of rectangles.
- arrow_right_alt
Find only the maximum height at any point rather than the full skyline contour.
- arrow_right_alt
Return a simplified skyline with merged horizontal segments of equal height.