LeetCode 218: The Skyline Problem (Sweep Line + Max-Heap)
LeetCode 218Sweep LineHeapToday we solve LeetCode 218 - The Skyline Problem.
Source: https://leetcode.com/problems/the-skyline-problem/
English
Problem Summary
Given rectangular buildings [left, right, height], return the skyline key points where the visible height changes when viewed from far away.
Key Insight
Convert each building into two events: entering at left and leaving at right. Sweep x from left to right and maintain active heights in a max-heap. The heap top is the current skyline height.
Algorithm
- Build events (x, -h, r) for starts and (x, 0, 0) for ends.
- Sort events by x, then by height marker.
- Maintain max-heap entries (-height, right).
- Before/after processing x, pop heap entries whose right <= x.
- If heap top height changes, append a new key point.
Complexity Analysis
Sorting events takes O(n log n). Each push/pop is O(log n), total O(n log n).
Space: O(n).
Common Pitfalls
- Not removing expired buildings before reading current height.
- Wrong tie handling when multiple events share same x.
- Appending duplicate heights consecutively.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
public List<List<Integer>> getSkyline(int[][] buildings) {
List<int[]> events = new ArrayList<>();
for (int[] b : buildings) {
events.add(new int[]{b[0], -b[2], b[1]});
events.add(new int[]{b[1], 0, 0});
}
events.sort((a, b) -> {
if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
return Integer.compare(a[1], b[1]);
});
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
pq.offer(new int[]{0, Integer.MAX_VALUE});
List<List<Integer>> ans = new ArrayList<>();
int prev = 0;
for (int[] e : events) {
int x = e[0], negH = e[1], r = e[2];
while (!pq.isEmpty() && pq.peek()[1] <= x) pq.poll();
if (negH != 0) pq.offer(new int[]{negH, r});
while (!pq.isEmpty() && pq.peek()[1] <= x) pq.poll();
int curr = -pq.peek()[0];
if (curr != prev) {
ans.add(Arrays.asList(x, curr));
prev = curr;
}
}
return ans;
}
}import "sort"
type pair struct{ h, r int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].h < h[j].h }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(x interface{}) { *h = append(*h, x.(pair)) }
func (h *hp) Pop() interface{} {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
func getSkyline(buildings [][]int) [][]int {
events := make([][3]int, 0, len(buildings)*2)
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 {
if events[i][0] != events[j][0] {
return events[i][0] < events[j][0]
}
return events[i][1] < events[j][1]
})
pq := &hp{{0, 1<<30}}
heap.Init(pq)
ans := [][]int{}
prev := 0
for _, e := range events {
x, nh, r := e[0], e[1], e[2]
for pq.Len() > 0 && (*pq)[0].r <= x {
heap.Pop(pq)
}
if nh != 0 {
heap.Push(pq, pair{nh, r})
}
for pq.Len() > 0 && (*pq)[0].r <= x {
heap.Pop(pq)
}
cur := -(*pq)[0].h
if cur != prev {
ans = append(ans, []int{x, cur})
prev = cur
}
}
return ans
}class Solution {
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
vector<array<int,3>> events;
for (auto &b : buildings) {
events.push_back({b[0], -b[2], b[1]});
events.push_back({b[1], 0, 0});
}
sort(events.begin(), events.end(), [](auto &a, auto &b){
if (a[0] != b[0]) return a[0] < b[0];
return a[1] < b[1];
});
priority_queue<pair<int,int>> pq;
pq.push({0, INT_MAX});
vector<vector<int>> ans;
int prev = 0;
for (auto &e : events) {
int x = e[0], nh = e[1], r = e[2];
while (!pq.empty() && pq.top().second <= x) pq.pop();
if (nh != 0) pq.push({-nh, r});
while (!pq.empty() && pq.top().second <= x) pq.pop();
int cur = pq.top().first;
if (cur != prev) {
ans.push_back({x, cur});
prev = cur;
}
}
return ans;
}
};import heapq
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()
# (negHeight, right)
heap = [(0, float('inf'))]
ans = []
prev = 0
for x, nh, r in events:
while heap and heap[0][1] <= x:
heapq.heappop(heap)
if nh != 0:
heapq.heappush(heap, (nh, r))
while heap and heap[0][1] <= x:
heapq.heappop(heap)
cur = -heap[0][0]
if cur != prev:
ans.append([x, cur])
prev = cur
return ans/**
* @param {number[][]} buildings
* @return {number[][]}
*/
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((a, b) => (a[0] - b[0]) || (a[1] - b[1]));
const heap = [[0, Number.MAX_SAFE_INTEGER]]; // [negHeight, right]
const push = (x) => {
heap.push(x);
let i = heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p][0] <= heap[i][0]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
};
const pop = () => {
const top = heap[0];
const last = heap.pop();
if (heap.length) {
heap[0] = last;
let i = 0;
while (true) {
let l = i * 2 + 1, r = l + 1, m = i;
if (l < heap.length && heap[l][0] < heap[m][0]) m = l;
if (r < heap.length && heap[r][0] < heap[m][0]) m = r;
if (m === i) break;
[heap[i], heap[m]] = [heap[m], heap[i]];
i = m;
}
}
return top;
};
const top = () => heap[0];
const ans = [];
let prev = 0;
for (const [x, nh, rr] of events) {
while (heap.length && top()[1] <= x) pop();
if (nh !== 0) push([nh, rr]);
while (heap.length && top()[1] <= x) pop();
const cur = -top()[0];
if (cur !== prev) {
ans.push([x, cur]);
prev = cur;
}
}
return ans;
};中文
题目概述
给定多个建筑物 [left, right, height]，返回天际线关键点，即可见高度发生变化的位置。
核心思路
把每个建筑拆成进入事件和离开事件，按 x 从小到大扫描。用最大堆维护当前仍覆盖 x 的建筑高度，堆顶就是当前天际线高度。
算法步骤
- 建立事件：起点 (x, -h, right)，终点 (x, 0, 0)。
- 事件按 x 排序，同 x 再按高度标记排序。
- 扫描到每个 x 时先弹出已过期建筑（right <= x）。
- 如果是起点事件则入堆。
- 读取堆顶高度，若与前一高度不同就记录关键点。
复杂度分析
排序是 O(n log n)，堆操作总计 O(n log n)。
空间复杂度：O(n)。
常见陷阱
- 读取高度前没先清理过期建筑。
- 同一 x 的事件处理顺序错误。
- 连续加入相同高度关键点，导致答案冗余。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
public List<List<Integer>> getSkyline(int[][] buildings) {
List<int[]> events = new ArrayList<>();
for (int[] b : buildings) {
events.add(new int[]{b[0], -b[2], b[1]});
events.add(new int[]{b[1], 0, 0});
}
events.sort((a, b) -> {
if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
return Integer.compare(a[1], b[1]);
});
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
pq.offer(new int[]{0, Integer.MAX_VALUE});
List<List<Integer>> ans = new ArrayList<>();
int prev = 0;
for (int[] e : events) {
int x = e[0], negH = e[1], r = e[2];
while (!pq.isEmpty() && pq.peek()[1] <= x) pq.poll();
if (negH != 0) pq.offer(new int[]{negH, r});
while (!pq.isEmpty() && pq.peek()[1] <= x) pq.poll();
int curr = -pq.peek()[0];
if (curr != prev) {
ans.add(Arrays.asList(x, curr));
prev = curr;
}
}
return ans;
}
}import "sort"
type pair struct{ h, r int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].h < h[j].h }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(x interface{}) { *h = append(*h, x.(pair)) }
func (h *hp) Pop() interface{} {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
func getSkyline(buildings [][]int) [][]int {
events := make([][3]int, 0, len(buildings)*2)
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 {
if events[i][0] != events[j][0] {
return events[i][0] < events[j][0]
}
return events[i][1] < events[j][1]
})
pq := &hp{{0, 1<<30}}
heap.Init(pq)
ans := [][]int{}
prev := 0
for _, e := range events {
x, nh, r := e[0], e[1], e[2]
for pq.Len() > 0 && (*pq)[0].r <= x {
heap.Pop(pq)
}
if nh != 0 {
heap.Push(pq, pair{nh, r})
}
for pq.Len() > 0 && (*pq)[0].r <= x {
heap.Pop(pq)
}
cur := -(*pq)[0].h
if cur != prev {
ans = append(ans, []int{x, cur})
prev = cur
}
}
return ans
}class Solution {
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
vector<array<int,3>> events;
for (auto &b : buildings) {
events.push_back({b[0], -b[2], b[1]});
events.push_back({b[1], 0, 0});
}
sort(events.begin(), events.end(), [](auto &a, auto &b){
if (a[0] != b[0]) return a[0] < b[0];
return a[1] < b[1];
});
priority_queue<pair<int,int>> pq;
pq.push({0, INT_MAX});
vector<vector<int>> ans;
int prev = 0;
for (auto &e : events) {
int x = e[0], nh = e[1], r = e[2];
while (!pq.empty() && pq.top().second <= x) pq.pop();
if (nh != 0) pq.push({-nh, r});
while (!pq.empty() && pq.top().second <= x) pq.pop();
int cur = pq.top().first;
if (cur != prev) {
ans.push_back({x, cur});
prev = cur;
}
}
return ans;
}
};import heapq
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()
heap = [(0, float('inf'))]
ans = []
prev = 0
for x, nh, r in events:
while heap and heap[0][1] <= x:
heapq.heappop(heap)
if nh != 0:
heapq.heappush(heap, (nh, r))
while heap and heap[0][1] <= x:
heapq.heappop(heap)
cur = -heap[0][0]
if cur != prev:
ans.append([x, cur])
prev = cur
return ans/**
* @param {number[][]} buildings
* @return {number[][]}
*/
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((a, b) => (a[0] - b[0]) || (a[1] - b[1]));
const heap = [[0, Number.MAX_SAFE_INTEGER]];
const push = (x) => {
heap.push(x);
let i = heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p][0] <= heap[i][0]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
};
const pop = () => {
const top = heap[0];
const last = heap.pop();
if (heap.length) {
heap[0] = last;
let i = 0;
while (true) {
let l = i * 2 + 1, r = l + 1, m = i;
if (l < heap.length && heap[l][0] < heap[m][0]) m = l;
if (r < heap.length && heap[r][0] < heap[m][0]) m = r;
if (m === i) break;
[heap[i], heap[m]] = [heap[m], heap[i]];
i = m;
}
}
return top;
};
const top = () => heap[0];
const ans = [];
let prev = 0;
for (const [x, nh, rr] of events) {
while (heap.length && top()[1] <= x) pop();
if (nh !== 0) push([nh, rr]);
while (heap.length && top()[1] <= x) pop();
const cur = -top()[0];
if (cur !== prev) {
ans.push([x, cur]);
prev = cur;
}
}
return ans;
};
Comments