天塌了。。公司直接集体降薪，同事18K变10K~

算法题：天际线问题

这道“天际线问题”，一看就不是实习生出的题，属于那种看起来跟图形学有关，其实是堆+扫描线结合的典范算法题。虽然它名字挺文艺，但你真写起来，会发现这玩意儿折磨得你脑壳疼 😵‍💫

题目描述大概是这样：给你一堆建筑，每个建筑是一段区间和一个高度，然后你得输出这些建筑堆起来之后，从远处看它的天际线轮廓。通俗点说，就是你得找出这些建筑在X轴上的“拐点”——每个拐点都是天际线变化的地方。

有点像什么？就像你站在一栋楼对面画剪影一样，哪些地方高了、哪些地方低了都要画出来...

好了废话少说，说点硬核的。常规思路你可能会想：是不是要先把这些建筑按左边界排序，再一栋一栋去模拟它的效果？别想太多，这么干肯定超时。因为你得不停地查最大高度、插入、删除，效率直接扑街。

真正靠谱的做法，是扫描线 + 最大堆（优先队列）。

思路是这样子的：

1. 把每栋建筑拆成两个点：进入点 (left, -height) 和离开点 (right, height)。注意进入点高度是负的，方便等会儿排序的时候先处理高的。
2. 把所有点按横坐标排序，如果横坐标相同，按高度排序。
3. 扫描所有点，遇到进入点就把高度放进堆里，遇到离开点就把高度从堆里移除（这点很坑）。
4. 每次扫描后，堆顶就是当前“天际线”的高度，跟上次不一样就记一笔。

代码不多，给你看下核心部分：

public List<List<Integer>> getSkyline(int[][] buildings) {
    List<int[]> points = new ArrayList<>();
for (int[] b : buildings) {
        points.add(newint[]{b[0], -b[2]}); // 进入点
        points.add(newint[]{b[1], b[2]});  // 离开点
    }

    points.sort((a, b) -> {
if (a[0] != b[0]) return a[0] - b[0]; // 横坐标升序
return a[1] - b[1]; // 高度升序（负数在前）
    });

    PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a); // 最大堆
    heap.add(0); // 地面高度
int prev = 0;
    List<List<Integer>> res = new ArrayList<>();

for (int[] p : points) {
if (p[1] < 0) {
            heap.add(-p[1]); // 进入
        } else {
            heap.remove(p[1]); // 离开（Java的堆移除不是O(logN)，这里是个坑）
        }
int curr = heap.peek();
if (curr != prev) {
            res.add(Arrays.asList(p[0], curr));
            prev = curr;
        }
    }
return res;
}

这个 heap.remove() 是个小坑，不是对堆内部结构的直接删除，它是遍历堆找元素然后重排，最差O(n)。所以这个写法在数据量大时性能会崩，如果你面试碰上这题，记得装一波——“我知道用TreeMap优化掉这个remove的复杂度”😉

实际项目里呢？这种题不常见，但你如果搞前端图形引擎或者高性能游戏引擎，扫描线算法可是老本行；还有做GIS系统或建筑规划模拟的后端也会碰见类似问题。

说回堆这个结构，它在Java里没什么存在感，大家用得最多的其实是PriorityQueue，但那玩意儿默认是最小堆，要搞最大堆得自定义Comparator，不然你一不小心就调成升序了，然后一通debug调到头秃...

另外说个冷知识：这题在LeetCode上是Hard级别，但其实它的核心套路在很多中等题里都能练，比如“合并区间”、“会议室安排”、“找最大重叠区间”等等，都是类似的处理。

写这题的时候我一开始也想简单了，想用一个Set存活跃的高度集合，但一旦遇到多个建筑有相同起点或终点，输出的拐点就不对了。最后还是老老实实地上堆，顺便复习一下TreeMap那点骚操作（TreeMap可以维护元素个数，不用担心堆里有重复）。

有兴趣的可以试试写个版本是用TreeMap替代堆的，看你性能能不能跑满；不过别指望生产环境真用这个解天际线，除非你公司是搞建筑仿真的 😅

对了，面试官如果追问你为啥负高度能解决排序优先级的问题，一定要解释清楚——负数让进入点优先排序，然后高的在前，这样才能保证天际线的“山头”不会被低的遮住。

下次你再看到一堆建筑从左往右排过去，不妨用脑子描一下这天际线，你会发现算法其实也挺浪漫的 🌆