LeetCode 218. 天际线问题——扫描线+堆的经典难题解法

老张2026/4/30大约 8 分钟

LeetCode 218. 天际线问题——扫描线+堆的经典难题解法

适读人群：Java 高级工程师、备战大厂 Hard 题的同学 | 阅读时长：约28分钟 | 难度：困难

开篇故事

天际线问题是扫描线算法和堆的结合使用的经典「硬核」题，也是我认为整个系列里理解门槛最高的题之一。

第一次见这道题，我以为是某种几何题。仔细读完发现：本质是把一组矩形的轮廓线合并成连续折线，找出折线的所有「拐点」。而这些拐点恰好出现在某个矩形的左边界（高度升高）或右边界（高度降低）时。

「高度变化」是关键词。每当从左到右扫描（扫描线），遇到新建筑物的左边缘，当前最高高度可能升高；遇到某建筑物的右边缘，当前最高高度可能降低。维护「当前最高高度」自然想到最大堆。

难点在于：如何正确处理同一 x 坐标上有多个事件，以及如何高效删除已经结束的建筑物。

一、题目解析

题目描述：

一个城市的天际线是从远处观看该城市中所有建筑物形成的轮廓。给你所有建筑物的位置和高度，请你返回由这些建筑物形成的天际线。

每个建筑物的格式为 [lefti, righti, heighti]，天际线的结果是一组关键点 [xi, yi] 的列表，这些关键点是天际线轮廓在 x 轴上的水平方向上从左到右的高度发生变化的点。

示例：

输入：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, newHeight]
建筑物结束时，如果高度降到 0（没有其他建筑物），记录 [x, 0]
多个建筑物同时开始/结束时，只记录一个拐点

二、解法一：暴力逐点扫描

思路分析

找到所有 x 坐标，对每个 x 坐标计算当前最高高度。

import java.util.*;

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        // 收集所有临界 x 坐标
        Set<Integer> xSet = new TreeSet<>();
        for (int[] b : buildings) {
            xSet.add(b[0]);
            xSet.add(b[1]);
        }
        
        List<List<Integer>> result = new ArrayList<>();
        int prevHeight = 0;
        
        for (int x : xSet) {
            // 计算 x 处的最高高度
            int maxHeight = 0;
            for (int[] b : buildings) {
                if (b[0] <= x && x < b[1]) {
                    maxHeight = Math.max(maxHeight, b[2]);
                }
            }
            
            if (maxHeight != prevHeight) {
                result.add(Arrays.asList(x, maxHeight));
                prevHeight = maxHeight;
            }
        }
        
        return result;
    }
}

复杂度分析

时间复杂度：O(n² log n)。n 个 x 坐标，每个 x 坐标扫描所有建筑物。
空间复杂度：O(n)。

三、解法二：分治合并

思路分析

天际线满足分治的条件：左半建筑物和右半建筑物的天际线可以分别求，然后合并。合并操作类似归并两个有序序列，双指针扫描，分别维护左右两组的当前最高高度，取较大值。

这里代码较长，给出核心思路：

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        return divide(buildings, 0, buildings.length - 1);
    }
    
    private List<List<Integer>> divide(int[][] buildings, int l, int r) {
        if (l == r) {
            // 单个建筑物的天际线：[left, height], [right, 0]
            List<List<Integer>> res = new ArrayList<>();
            res.add(Arrays.asList(buildings[l][0], buildings[l][2]));
            res.add(Arrays.asList(buildings[l][1], 0));
            return res;
        }
        int mid = (l + r) / 2;
        return merge(divide(buildings, l, mid), divide(buildings, mid + 1, r));
    }
    
    private List<List<Integer>> merge(List<List<Integer>> left, List<List<Integer>> right) {
        List<List<Integer>> result = new ArrayList<>();
        int i = 0, j = 0;
        int h1 = 0, h2 = 0; // 左右当前高度
        
        while (i < left.size() && j < right.size()) {
            int x, h;
            if (left.get(i).get(0) < right.get(j).get(0)) {
                x = left.get(i).get(0);
                h1 = left.get(i++).get(1);
            } else if (left.get(i).get(0) > right.get(j).get(0)) {
                x = right.get(j).get(0);
                h2 = right.get(j++).get(1);
            } else {
                x = left.get(i).get(0);
                h1 = left.get(i++).get(1);
                h2 = right.get(j++).get(1);
            }
            h = Math.max(h1, h2);
            if (result.isEmpty() || result.get(result.size() - 1).get(1) != h) {
                result.add(Arrays.asList(x, h));
            }
        }
        
        while (i < left.size()) result.add(left.get(i++));
        while (j < right.size()) result.add(right.get(j++));
        
        return result;
    }
}

复杂度分析

时间复杂度：O(n log n)。分治 log n 层，每层合并 O(n)。
空间复杂度：O(n log n)。递归栈 + 中间结果。

四、解法三（最优）：扫描线 + 最大堆

核心思想

将每个建筑物拆成两个事件：

左边缘：(x, -height)（负号表示开始，方便排序时同一 x 坐标左边缘优先处理）
右边缘：(x, height)（正数表示结束）

将所有事件按 x 坐标排序，相同 x 坐标：

左边缘（高的在前）优先（同时出现的左边缘，高的先处理）
右边缘（矮的在前）优先（同时出现的右边缘，矮的先处理，确保高楼还在天际线上）
左边缘优先于右边缘（同一 x 有开始有结束时，先开始再结束）

维护最大堆，存当前「有效」建筑物的高度（加入左边缘时入堆，右边缘时懒删除）。

完整代码

import java.util.*;

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        // 展开所有事件：[x, height] 其中左边缘高度用负数表示
        List<int[]> events = new ArrayList<>();
        for (int[] b : buildings) {
            events.add(new int[]{b[0], -b[2]}); // 左边缘，高度取负
            events.add(new int[]{b[1], b[2]});  // 右边缘，高度取正
        }
        
        // 排序规则：
        // 1. x 坐标小的在前
        // 2. 同一 x：左边缘（负高度）在前（-10 < 0 < 5，负数更小）
        //    同为左边缘：高度绝对值大的在前（-15 < -10，先处理高楼）
        //    同为右边缘：高度小的在前（5 < 10，先结束矮楼）
        events.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        
        List<List<Integer>> result = new ArrayList<>();
        
        // 最大堆（懒删除），存有效建筑物高度
        // 使用 TreeMap 记录每个高度的建筑物数量（代替纯最大堆+懒删除）
        TreeMap<Integer, Integer> heightMap = new TreeMap<>();
        heightMap.put(0, 1); // 地面高度（作为哨兵）
        
        int prevMaxHeight = 0;
        
        for (int[] event : events) {
            int x = event[0];
            int h = event[1];
            
            if (h < 0) {
                // 左边缘：建筑物开始，加入高度
                heightMap.merge(-h, 1, Integer::sum);
            } else {
                // 右边缘：建筑物结束，移除高度
                heightMap.merge(h, -1, Integer::sum);
                if (heightMap.get(h) == 0) heightMap.remove(h);
            }
            
            // 当前最高高度
            int currMaxHeight = heightMap.lastKey();
            
            // 如果最高高度发生变化，记录拐点
            if (currMaxHeight != prevMaxHeight) {
                result.add(Arrays.asList(x, currMaxHeight));
                prevMaxHeight = currMaxHeight;
            }
        }
        
        return result;
    }
}