天际线问题 图解题解

这道题到底在问什么

buildings

[[1,4,3],[3,6,4],[5,8,2]]

A / B / C

高 3 / 高 4 / 高 2

输出

[[1,3],[3,4],[6,2],[8,0]]

先想最直接的笨办法

A[1,4) 拆成「x=1 进场」「x=4 退场」;B[3,6) 拆成「x=3 进」「x=6 退」;C[5,8) 拆成「x=5 进」「x=8 退」。6 个事件按 x 排好队:1,3,4,5,6,8。指针从最左开始,一个一个处理。（动画第 5 步）

最优解：一步一步想明白

1. 3高度只会在楼的边界处变化:有楼进场(左边)可能变高,有楼退场(右边)可能变矮。所以我们只需盯住所有楼的左右端点,在这些 x 处检查当前最高高度。
2. 4把每栋楼拆成两个事件:左端=进场、右端=退场。所有事件按 x 排序,从左到右逐个处理。进场就把高度丢进大根堆,堆顶永远是当前最高;退场的楼到期了就清出去。堆顶高度一变,就记一个关键点。
3. 53 栋楼 → 6 个事件,按 x 升序A[1,4) 拆成「x=1 进场」「x=4 退场」;B[3,6) 拆成「x=3 进」「x=6 退」;C[5,8) 拆成「x=5 进」「x=8 退」。6 个事件按 x 排好队:1,3,4,5,6,8。指针从最左开始,一个一个处理。
4. 6下面用楼栋图看轮廓怎么长出来,用大根堆看高度怎么维护。盯住三样:扫描线 x(从左推到右)、大根堆堆顶(当前最高)、关键点(堆顶一变就记一笔)。
5. 7扫描线还没出发,堆里只有地面 0正式开扫前,场上一栋楼都没进来,当前最高 = 地面 0。下面这 7 个台阶位代表 x=1~8 的各段轮廓,先全是 0;扫描线从最左往右推,每处理一个事件就可能抬高或压低某段。
6. 8堆 push 3 → 堆顶 3,比之前(0)高 → 记点扫描线推到 x=1,A 进场,高度 3 丢进堆。堆里原本只有「地面 0」,现在堆顶变成 3——比之前的 0 高了,高度变化了,记下第一个关键点 [1,3]。轮廓从地面升到 3。
7. 9堆(按高度):[3, 0地面]堆里永远在堆底垫一个「地面 0」(右端当无穷大、永不退场),这样所有楼都退场后堆顶自然是 0,轮廓落地。现在堆顶是 A 的 3。
8. 10堆 push 4 → 堆顶 3→4,更高 → 记点扫描线到 x=3,B(高 4)进场入堆。此刻 A、B 都在场,堆顶从 3 升到 4(B 更高)。高度变了,记关键点 [3,4]。注意 x=1~3 这段轮廓仍是 A 的高度 3。
9. 11新元素 4 先放末尾:[3, 0, 4]入堆分两步。第一步:B 的高度 4 先塞到堆的最末尾。它的父亲是堆顶 3,可 4 比 3 大,违反了「父 ≥ 子」的大根堆规矩,接下来让它往上冒。
10. 124 与父亲 3 交换:[4, 0, 3],堆顶=4第二步「上浮」:4 和父亲 3 比,4 更大就交换,一路往上冒到顶。现在堆顶是 B 的 4,3(A)沉下去当孩子。这就是堆维持「堆顶最大」的内部动作。
11. 13A 到期,但堆顶仍是 B 的 4 → 高度没变,不记点扫描线到 x=4,这是 A 的右端,A 退场。但当前最高是 B 的 4,A 本来就不是堆顶,它走不走不影响堆顶。堆顶还是 4,高度没变,不记关键点。x=3~4 这段轮廓延续 4。
12. 14A 的 3 不在堆顶 → 懒删除,先不动大根堆只能从堆顶取走元素,没法直接抠出中间的 A。用「懒删除」:每个高度都记着自己的右端,过期了先不管,等它升到堆顶时(下次取堆顶前)再统一清掉。所以堆里给每个高度都带了「右端」这个标签。
13. 15堆 push 2,但 2 < 堆顶 4 → 高度没变,不记点扫描线到 x=5,C(高 2)进场入堆。但 C 才 2,比当前堆顶 4(B)矮,沉到堆里当孩子,堆顶还是 4。高度没变,不记点。此刻在场的有 B(4)和 C(2),最高仍是 4。
14. 162 < 堆顶,挂末尾不用上浮:[4, 0, 3, ?, 2]C 的高度 2 入堆,它远小于堆顶 4,不会浮上来,堆顶纹丝不动。注意此刻堆里还混着已过期的 A(3),但它没在堆顶、暂时不碍事——这正是懒删除「先留着」的样子。
15. 17B 是堆顶且右端6≤6 → 弹出 B扫描线到 x=6,B 的右端到了。取当前最高前先清栈:堆顶 B(右端 6)≤ 6,过期,弹出!之前那段(x=4~6)轮廓维持的 4 到这里结束。把灰掉的旧楼清出去后,看看新堆顶是谁。
16. 18堆顶 B(右端6)过期 → pop,末尾补位弹掉 B 后,之前一直赖在堆里的过期 A(高 3)这下浮到了堆顶。它的右端 4 也早 ≤ 6——所以清栈不止弹一次,要一直弹到堆顶不再过期为止。这就是懒删除「攒到一起清」的时刻。
17. 19堆顶 A(右端4)也过期 → 再 pop,堆顶=2再弹掉过期的 A,堆顶变成 C 的 2(右端 8,还没过期,停止清栈)。当前最高从 4 掉到 2,高度变了,记关键点 [6,2]。轮廓在 x=6 从 4 跌到 2。
18. 20记下 [6,2],只剩 C 在场B 走了,场上只剩 C(高 2)。x=6 起轮廓降到 2。看楼栋图:左边 4 的台阶到 x=6 结束,接上 C 的矮台阶 2。关键点 [6,2] 正是这个下降的拐角。
19. 21C 出堆,堆里只剩地面 0 → 记 [8,0]扫描线到 x=8,C 的右端到了。清栈弹掉堆顶 C(右端 8 ≤ 8),堆里只剩垫底的地面 0。当前最高 4...不,是 0——没楼了,轮廓落回地面。记最后一个关键点 [8,0]。
20. 22拿走堆顶 C,末尾的地面 0 搬到顶补空再看一眼「取堆顶」的内部动作:不是直接抠掉堆顶,而是把末尾元素搬到顶补空,再让它和孩子比、必要时一路下沉归位。这里末尾正好是地面 0,搬上来即合法。
21. 23堆顶 C 过期弹出 → 堆顶=0(地面)幸亏堆底一直垫着「地面 0」:所有楼退场后,堆顶自然是 0,轮廓优雅落地。这就是为什么初始化时往堆里塞一个高度 0、右端无穷大的哨兵——省去判空的麻烦。
22. 24关键点 [1,3][3,4][6,2][8,0]整条天际线就是这串台阶:x=1 升到 3,x=3 升到 4(B 盖过 A),x=6 跌到 2(只剩 C),x=8 落地 0。4 个关键点 [1,3]、[3,4]、[6,2]、[8,0] 标出每个高度变化的拐角,和手算、和代码实跑完全一致。
23. 25别被「进场就升、退场就降」骗了。x=4 A 退场但堆顶没变(B 更高)、x=5 C 进场但堆顶没变(C 太矮),都不记点。轮廓只在「当前最高换了高度」时拐弯,这个判断完全交给堆顶。
24. 26O(范围·n) → O(n log n)关键提速两点:① 只在端点处理(2n 个),不管中间无变化的坐标;② 用大根堆把「当前最高」从每次 O(n) 重扫降到取堆顶 O(1)、维护 O(log n)。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

import heapq
class Solution:
    def getSkyline(self, buildings):
        events = []
        for L, R, H in buildings:
            events.append((L, -H, R))   # 进场:负高度
            events.append((R, 0, 0))    # 退场
        events.sort()                    # 按 x 升序
        res = []
        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))
            curH = -heap[0][0]           # 当前最高
            if not res or res[-1][1] != curH:  # 变了才记
                res.append([x, curH])
        return res

class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        vector<array<int,3>> events;  // (x, negH, R)
        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());
        vector<vector<int>> res;
        priority_queue<pair<int,int>> heap;  // (高, 右端) 大根堆
        heap.push({0, INT_MAX});             // 垫地面
        for (auto& e : events) {
            int x = e[0], H = -e[1], R = e[2];
            while (heap.top().second <= x) heap.pop();  // 清栈
            if (e[1]) heap.push({H, R});         // 进场入堆
            int curH = heap.top().first;
            if (res.empty() || res.back()[1] != curH)
                res.push_back({x, curH});
        }
        return res;
    }
};

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(new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[0] != b[0] ? a[0] - b[0] : a[1] - b[1];
            }
        });
        List<List<Integer>> res = new ArrayList<>();
        PriorityQueue<int[]> heap = new PriorityQueue<>(
            new Comparator<int[]>() {
                public int compare(int[] a, int[] b) { return b[0] - a[0]; }
            });
        heap.offer(new int[]{0, Integer.MAX_VALUE});   // 垫地面
        for (int[] e : events) {
            int x = e[0], H = -e[1], R = e[2];
            while (heap.peek()[1] <= x) heap.poll();   // 清栈
            if (e[1] != 0) heap.offer(new int[]{H, R});
            int curH = heap.peek()[0];
            if (res.isEmpty() || res.get(res.size()-1).get(1) != curH) {
                List<Integer> p = new ArrayList<>();
                p.add(x); p.add(curH);
                res.add(p);
            }
        }
        return res;
    }
}

复杂度

面试官可能追问