218. 天际线问题

Hard

题目描述

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

每个建筑物的几何信息用数组 buildings 表示，其中 buildings[i] = [lefti, righti, heighti]：

lefti 是第 i 座建筑物左边缘的 x 坐标。
righti 是第 i 座建筑物右边缘的 x 坐标。
heighti 是第 i 座建筑物的高度。

可以假设所有建筑物都是在绝对平坦的表面上的完美矩形，高度为 0。

天际线应该表示为按 x 坐标排序的"关键点"列表，形式为 [[x1,y1],[x2,y2],...]。每个关键点都是天际线中某个水平线段的左端点，除了列表中的最后一个点，它的 y 坐标始终为 0，用于标记天际线在最右边建筑物结束处的终止。最左边和最右边建筑物之间的任何地面都应该是天际线轮廓的一部分。

注意： 输出的天际线中不能有连续的相同高度的水平线。例如，[...,[2 3],[4 5],[7 5],[11 5],[12 7],...] 是不可接受的；高度为 5 的三条线应该合并为一条：[...,[2 3],[4 5],[12 7],...]

示例 1：

输入：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]]

示例 2：

输入：buildings = [[0,2,3],[2,5,3]]
输出：[[0,3],[5,0]]

提示：

1 <= buildings.length <= 10^4
0 <= lefti < righti <= 2^31 - 1
1 <= heighti <= 2^31 - 1
buildings 按 lefti 非递减顺序排序。

解题思路

这道题是经典的扫描线算法问题。核心思路是将所有建筑物的左右边界作为关键事件点，然后从左到右扫描这些事件点，维护当前所有活跃建筑物的最大高度。

算法思路：

事件点提取：将每个建筑物转换为两个事件：
- 左边界事件：(x, height, 'start')
- 右边界事件：(x, height, 'end')
事件排序：按 x 坐标排序，相同 x 坐标时需要特殊处理：
- 开始事件优先于结束事件
- 开始事件中高度大的优先
- 结束事件中高度小的优先
扫描处理：使用多重集合（multiset）或优先队列维护当前活跃建筑物的高度：
- 遇到开始事件时，添加该高度
- 遇到结束事件时，移除该高度
- 检查最大高度是否发生变化，如有变化则记录关键点
优化细节：相同 x 坐标的所有事件一次性处理，避免产生多余的关键点。

这种方法的关键在于正确处理边界情况和事件排序，确保天际线的连续性和正确性。

代码实现

class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        vector<pair<int, int>> events; // (x, height), height > 0 为开始，< 0 为结束
        
        for (auto& building : buildings) {
            events.push_back({building[0], building[2]});     // 开始事件
            events.push_back({building[1], -building[2]});    // 结束事件
        }
        
        sort(events.begin(), events.end(), [](const pair<int,int>& a, const pair<int,int>& b) {
            if (a.first != b.first) return a.first < b.first;
            return a.second < b.second; // 开始事件(正数)排在结束事件(负数)前面
        });
        
        vector<vector<int>> result;
        multiset<int> heights;
        heights.insert(0); // 地面高度
        
        int i = 0;
        while (i < events.size()) {
            int currentX = events[i].first;
            
            // 处理所有相同x坐标的事件
            while (i < events.size() && events[i].first == currentX) {
                if (events[i].second > 0) {
                    heights.insert(events[i].second);
                } else {
                    heights.erase(heights.find(-events[i].second));
                }
                i++;
            }
            
            int maxHeight = *heights.rbegin();
            if (result.empty() || result.back()[1] != maxHeight) {
                result.push_back({currentX, maxHeight});
            }
        }
        
        return result;
    }
};

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        import heapq
        from collections import defaultdict
        
        events = []
        for left, right, height in buildings:
            events.append((left, height, 's'))    # 开始事件
            events.append((right, height, 'e'))   # 结束事件
        
        # 排序：x坐标优先，相同x时开始事件优先，开始事件中高度大的优先
        events.sort(key=lambda x: (x[0], x[2] == 'e', -x[1] if x[2] == 's' else x[1]))
        
        result = []
        max_heap = [0]  # 使用负数实现最大堆
        height_count = defaultdict(int)
        height_count[0] = 1
        
        i = 0
        while i < len(events):
            current_x = events[i][0]
            
            # 处理所有相同x坐标的事件
            while i < len(events) and events[i][0] == current_x:
                x, height, event_type = events[i]
                if event_type == 's':
                    heapq.heappush(max_heap, -height)
                    height_count[height] += 1
                else:
                    height_count[height] -= 1
                    if height_count[height] == 0:
                        del height_count[height]
                i += 1
            
            # 清理堆顶的无效高度
            while max_heap and -max_heap[0] not in height_count:
                heapq.heappop(max_heap)
            
            max_height = -max_heap[0]
            if not result or result[-1][1] != max_height:
                result.append([current_x, max_height])
        
        return result

public class Solution {
    public IList<IList<int>> GetSkyline(int[][] buildings) {
        var events = new List<(int x, int height, char type)>();
        
        foreach (var building in buildings) {
            events.Add((building[0], building[2], 's')); // 开始事件
            events.Add((building[1], building[2], 'e')); // 结束事件
        }
        
        // 排序：x坐标优先，相同x时开始事件优先，开始事件中高度大的优先
        events.Sort((a, b) => {
            if (a.x != b.x) return a.x.CompareTo(b.x);
            if (a.type != b.type) return a.type.CompareTo(b.type);
            return a.type == 's' ? b.height.CompareTo(a.height) : a.height.CompareTo(b.height);
        });
        
        var result = new List<IList<int>>();
        var heights = new SortedDictionary<int, int> { {0, 1} };
        
        int i = 0;
        while (i < events.Count) {
            int currentX = events[i].x;
            
            // 处理所有相同x坐标的事件
            while (i < events.Count && events[i].x == currentX) {
                var (x, height, type) = events[i];
                if (type == 's') {
                    heights[height] = heights.GetValueOrDefault(height, 0) + 1;
                } else {
                    heights[height]--;
                    if (heights[height] == 0) {
                        heights.Remove(height);
                    }
                }
                i++;
            }
            
            int maxHeight = heights.Keys.Max();
            if (result.Count == 0 || result[result.Count - 1][1] != maxHeight) {
                result.Add(new List<int> { currentX, maxHeight });
            }
        }
        
        return result;
    }
}

var getSkyline = function(buildings) {
    const events = [];
    
    for (const [left, right, height] of buildings) {
        events.push([left, height, 's']);   // 开始事件
        events.push([right, height, 'e']);  // 结束事件
    }
    
    // 排序：x坐标优先，相同x时开始事件优先，开始事件中高度大的优先
    events.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        if (a[2] !== b[2]) return a[2].localeCompare(b[2]);
        return a[2]

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	值	说明
时间复杂度	O(n log n)	n为建筑物数量，主要消耗在事件排序和维护有序集合
空间复杂度	O(n)	存储事件列表和高度集合

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目