天际线问题（Skyline Problem）是计算几何与分治算法的经典结合。给定城市中若干建筑物的左右边界和高度，求从远处看去建筑物的轮廓线——即所有建筑物的并集所形成的上边界折线。本文用Java实现基于扫描线（Sweep Line）和最大堆的高效解法。
问题分析
每座建筑物用三元组 $[L, R, H]$ 表示，其中 $L$ 为左边界横坐标，$R$ 为右边界横坐标，$H$ 为高度。天际线由一系列关键点 $(x, h)$ 组成，表示在位置 $x$ 处轮廓线的高度变为 $h$。
关键观察：天际线只在建筑物的左右边界处发生变化。当进入一个建筑物范围时，高度可能上升；当离开最高建筑物时，高度下降为次高建筑物的高度。
算法核心思想
扫描线算法
- 事件生成：将每座建筑物的左右边界转换为事件。左边界为”进入事件”（高度为正），右边界为”离开事件”（高度为负或标记删除）
- 事件排序：按横坐标排序，同一位置先处理进入事件（高度高的优先）
- 最大堆维护：用最大堆维护当前活跃的建筑物高度
- 遇到左边界：将高度加入堆
- 遇到右边界：从堆中移除对应高度
- 每次事件后，如果堆顶高度发生变化，则产生一个天际线关键点
关键细节
由于Java的PriorityQueue是最小堆，需要自定义比较器实现最大堆。更复杂的是，标准的堆不支持高效的任意元素删除，因此需要采用延迟删除策略：使用一个额外的哈希表记录待删除的高度，当堆顶恰好是待删除元素时才真正移除。
Java完整实现
import java.util.*;
/**
* 天际线问题 - 扫描线算法 + 最大堆实现
* 给定建筑物集合，求从远处看到的天际线轮廓
*/
public class SkylineProblem {
/**
* 建筑物类
*/
static class Building {
int left, right, height;
Building(int l, int r, int h) {
left = l; right = r; height = h;
}
}
/**
* 事件类：用于扫描线
*/
static class Event {
int x; // 事件位置
int height; // 建筑物高度
boolean isStart; // true=进入事件, false=离开事件
int buildingId; // 建筑物标识
Event(int x, int h, boolean start, int id) {
this.x = x;
this.height = h;
this.isStart = start;
this.buildingId = id;
}
}
/**
* 主解法：扫描线 + 最大堆（延迟删除）
* @param buildings 建筑物数组，每座 [left, right, height]
* @return 天际线关键点列表 [x, height]
*/
public static List<int[]> getSkyline(int[][] buildings) {
List<int[]> result = new ArrayList<>();
if (buildings == null || buildings.length == 0) {
return result;
}
// 1. 生成所有事件
List<Event> events = new ArrayList<>();
for (int i = 0; i < buildings.length; i++) {
events.add(new Event(buildings[i][0], buildings[i][2], true, i));
events.add(new Event(buildings[i][1], buildings[i][2], false, i));
}
// 2. 排序事件：按x坐标升序，同一x先处理进入事件（高度降序）
events.sort((a, b) -> {
if (a.x != b.x) {
return Integer.compare(a.x, b.x);
}
// 同一位置：进入事件先于离开事件
if (a.isStart && !b.isStart) {
return -1;
}
if (!a.isStart && b.isStart) {
return 1;
}
// 同为进入事件：高度高的优先
if (a.isStart) {
return Integer.compare(b.height, a.height);
}
// 同为离开事件：高度低的优先（先移除矮的，避免影响当前最高）
return Integer.compare(a.height, b.height);
});
// 3. 最大堆 + 延迟删除
// 堆中存储高度，使用延迟删除处理右边界事件
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// 记录每个高度出现的次数（处理高度相同的建筑物）
Map<Integer, Integer> heightCount = new HashMap<>();
// 延迟删除计数
Map<Integer, Integer> removedCount = new HashMap<>();
int prevMaxHeight = 0;
maxHeap.offer(0); // 地面高度
heightCount.put(0, 1);
int i = 0;
while (i < events.size()) {
int currX = events.get(i).x;
// 处理当前x位置的所有事件
while (i < events.size() && events.get(i).x == currX) {
Event e = events.get(i);
if (e.isStart) {
// 进入事件：加入堆
maxHeap.offer(e.height);
heightCount.merge(e.height, 1, Integer::sum);
} else {
// 离开事件：标记延迟删除
removedCount.merge(e.height, 1, Integer::sum);
}
i++;
}
// 清理堆顶已删除的元素
while (!maxHeap.isEmpty()) {
int top = maxHeap.peek();
int rem = removedCount.getOrDefault(top, 0);
int cnt = heightCount.getOrDefault(top, 0);
if (rem > 0 && rem >= cnt) {
maxHeap.poll();
removedCount.remove(top);
heightCount.remove(top);
} else if (rem > 0) {
// 部分删除
break;
} else {
break;
}
}
// 获取当前最大高度
int currMaxHeight = maxHeap.isEmpty() ? 0 : maxHeap.peek();
// 如果高度发生变化，记录关键点
if (currMaxHeight != prevMaxHeight) {
result.add(new int[]{currX, currMaxHeight});
prevMaxHeight = currMaxHeight;
}
}
return result;
}
/**
* 分治解法：归并两个天际线
*/
public static List<int[]> getSkylineDivideConquer(int[][] buildings) {
if (buildings == null || buildings.length == 0) {
return new ArrayList<>();
}
return mergeSkyline(buildings, 0, buildings.length - 1);
}
private static List<int[]> mergeSkyline(int[][] buildings, int left, int right) {
if (left == right) {
List<int[]> res = new ArrayList<>();
res.add(new int[]{buildings[left][0], buildings[left][2]});
res.add(new int[]{buildings[left][1], 0});
return res;
}
int mid = left + (right - left) / 2;
List<int[]> leftSkyline = mergeSkyline(buildings, left, mid);
List<int[]> rightSkyline = mergeSkyline(buildings, mid + 1, right);
return mergeTwoSkylines(leftSkyline, rightSkyline);
}
private static List<int[]> mergeTwoSkylines(List<int[]> left, List<int[]> right) {
List<int[]> result = new ArrayList<>();
int i = 0, j = 0;
int h1 = 0, h2 = 0; // 当前左右天际线的高度
while (i < left.size() && j < right.size()) {
int x, maxH;
if (left.get(i)[0] < right.get(j)[0]) {
x = left.get(i)[0];
h1 = left.get(i)[1];
maxH = Math.max(h1, h2);
i++;
} else if (left.get(i)[0] > right.get(j)[0]) {
x = right.get(j)[0];
h2 = right.get(j)[1];
maxH = Math.max(h1, h2);
j++;
} else {
x = left.get(i)[0];
h1 = left.get(i)[1];
h2 = right.get(j)[1];
maxH = Math.max(h1, h2);
i++;
j++;
}
// 避免连续相同高度的点
if (result.isEmpty() || result.get(result.size() - 1)[1] != maxH) {
result.add(new int[]{x, maxH});
}
}
while (i < left.size()) {
result.add(left.get(i++));
}
while (j < right.size()) {
result.add(right.get(j++));
}
// 合并相同高度的相邻点
List<int[]> cleaned = new ArrayList<>();
for (int[] point : result) {
if (cleaned.isEmpty() || cleaned.get(cleaned.size() - 1)[1] != point[1]) {
cleaned.add(point);
}
}
return cleaned;
}
/**
* 打印天际线
*/
public static void printSkyline(List<int[]> skyline) {
System.out.println("天际线关键点:");
for (int[] point : skyline) {
System.out.printf(" x=%d, height=%d%n", point[0], point[1]);
}
// 文本可视化
System.out.println("\n文本可视化（简化）:");
int maxH = skyline.stream().mapToInt(p -> p[1]).max().orElse(0);
for (int h = maxH; h > 0; h--) {
System.out.printf("H=%2d ", h);
for (int[] point : skyline) {
if (point[1] >= h) {
System.out.print("██");
} else {
System.out.print(" ");
}
}
System.out.println();
}
}
public static void main(String[] args) {
int[][] buildings = {
{2, 9, 10},
{3, 7, 15},
{5, 12, 12},
{15, 20, 10},
{19, 24, 8}
};
System.out.println("=== 扫描线算法 ===");
List<int[]> skyline1 = getSkyline(buildings);
printSkyline(skyline1);
System.out.println("\n=== 分治算法 ===");
List<int[]> skyline2 = getSkylineDivideConquer(buildings);
printSkyline(skyline2);
// 验证两种方法结果一致
boolean match = skyline1.size() == skyline2.size();
if (match) {
for (int i = 0; i < skyline1.size(); i++) {
if (skyline1.get(i)[0] != skyline2.get(i)[0] ||
skyline1.get(i)[1] != skyline2.get(i)[1]) {
match = false;
break;
}
}
}
System.out.println("\n两种算法结果一致: " + match);
}
}
时间复杂度分析
扫描线算法
- 事件生成：$O(n)$
- 事件排序：$O(n \log n)$
- 扫描处理：每个事件涉及堆操作 $O(\log n)$，共 $2n$ 个事件，总计 $O(n \log n)$
- 总时间复杂度：$O(n \log n)$
- 空间复杂度：$O(n)$，存储事件和堆
分治算法
- 递归关系：$T(n) = 2T(n/2) + O(n)$
- 总时间复杂度：$O(n \log n)$
- 空间复杂度：$O(n \log n)$，递归栈和中间结果
两种算法时间复杂度相同，但扫描线算法的常数因子更小，且空间效率更优。
算法变体
实际问题中可能需要考虑：
– 最大矩形：在直方图中找到最大矩形面积（可用单调栈优化到 $O(n)$）
– 雨水收集：计算建筑物间的积水总量（双指针法 $O(n)$）
– 二维天际线：扩展到三维空间的建筑并集体积计算
