LeetCode 218. 天际线问题

2021-08-30 HGNULB 约 8 分钟

文章信息 6 个分类 8 个标签

分类

LeetCode CodeTop 困难未解决 1-2 字节

题目描述

✅ 218. 天际线问题

题意分析

每栋建筑给出左边界、右边界和高度。对每个横坐标，轮廓高度是覆盖该位置的所有建筑中的最大高度，没有建筑覆盖时为 0。

只输出高度发生变化的位置 [x, height]，其中 height 表示从 x 开始向右的轮廓高度。相邻关键点不能具有相同高度，建筑之间的空隙和最后落回地面的位置也必须体现。

解法：扫描线 + 高度多重集合

核心思路

[!blue]

轮廓只可能在建筑的左右边界处变化：相邻边界之间没有建筑开始或结束，覆盖的建筑集合不变，最大高度也不变。因此把每栋建筑拆成两个事件：左边界加入高度，右边界移除高度，再按横坐标从小到大扫描。

代码用负高度表示加入事件、正高度表示移除事件。处理横坐标 x 后，保留的建筑满足 left <= x < right，它们决定从 x 向右的真实高度。同一横坐标可能同时有建筑开始和结束，必须全部更新后再读取最高值；逐条事件的中间状态并不对应一段真实的轮廓。

活跃高度必须记录次数，而不能只存是否存在。同一高度可能来自多栋建筑，结束一栋时只减少一次计数，只有次数降为 0 才表示这个高度不再有效。

Java 使用 TreeMap<高度, 次数>，计数归零时删除键，lastKey() 就是当前最高高度。Go 使用计数表和最大堆：开始事件把高度压入堆，结束事件只减少计数；读取最高值前，反复弹出计数为 0 的堆顶。失效高度留在堆内较低位置不会影响当前最大值，等它浮到堆顶再清理即可。

堆中可能有同一高度的多个副本，但查询只关心这个高度是否仍有建筑有效。只要计数大于 0，该高度就可以代表轮廓；计数为 0 时，相关副本会在到达堆顶后依次被清理。

预先加入一份高度 0，代表始终存在的地面，使最高值总有定义。每组事件结束后，将当前高度与 prevHeight 比较，只有不同才记录关键点。这样不会产生同坐标的假转折，也不会输出连续的相同高度；最后一栋建筑结束时会自然记录高度 0。

解题步骤

为每栋建筑建立 [left, -height] 和 [right, height] 两个事件，按横坐标排序。

初始化高度 0 的计数和上一次轮廓高度 0；Go 同时把地面高度放入最大堆。

取当前横坐标 x，一次处理完所有发生在 x 的加入、移除事件，更新高度计数。

Java 读取有序映射的最大键；Go 先清理零计数的堆顶，再读取最大值。

如果当前最高值不同于上次高度，追加 [x, 当前高度] 并更新上次高度，然后继续下一组事件。

代码实现

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        int[][] events = new int[buildings.length * 2][2];
        int index = 0;

        for (int[] building : buildings) {
            events[index++] = new int[] {
                building[0],
                -building[2]
            };
            events[index++] = new int[] {
                building[1],
                building[2]
            };
        }

        Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0]));

        TreeMap<Integer, Integer> heightCount = new TreeMap<>();

        // 地面始终有效，建筑全部结束后最高值自然回到零。
        heightCount.put(0, 1);
        List<List<Integer>> res = new ArrayList<>();
        int i = 0;
        int prevHeight = 0;

        while (i < events.length) {
            int x = events[i][0];

            // 同一坐标的事件全部更新后，才能读取最终轮廓。
            while (i < events.length && events[i][0] == x) {
                int height = events[i][1];

                if (height < 0) {
                    int actualHeight = -height;

                    heightCount.put(actualHeight, heightCount.getOrDefault(actualHeight, 0) + 1);
                } else {
                    int count = heightCount.get(height);

                    if (count == 1) {
                        heightCount.remove(height);
                    } else {
                        heightCount.put(height, count - 1);
                    }
                }

                i++;
            }

            int curHeight = heightCount.lastKey();

            if (curHeight != prevHeight) {
                res.add(Arrays.asList(x, curHeight));
                prevHeight = curHeight;
            }
        }

        return res;
    }
}

import (
    "container/heap"
    "sort"
)

type maxHeap []int

func (h maxHeap) Len() int { return len(h) }

func (h maxHeap) Less(i, j int) bool { return h[i] > h[j] }

func (h maxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *maxHeap) Push(value any) {
    *h = append(*h, value.(int))
}

func (h *maxHeap) Pop() any {
    old := *h
    value := old[len(old)-1]
    *h = old[:len(old)-1]
    return value
}

func getSkyline(buildings [][]int) [][]int {
    events := make([][2]int, 0, len(buildings)*2)
    for _, building := range buildings {
        events = append(events, [2]int{
            building[0],
            -building[2],
        })
        events = append(events, [2]int{
            building[1],
            building[2],
        })
    }
    sort.Slice(events, func(i, j int) bool {
        return events[i][0] < events[j][0]
    })

    // 地面始终有效，建筑全部结束后最高值自然回到零。
    heightCount := map[int]int{0: 1}
    heights := &maxHeap{
        0,
    }
    heap.Init(heights)
    result := make([][]int, 0)
    previousHeight := 0

    for i := 0; i < len(events); {
        x := events[i][0]
        // 同一坐标的事件全部更新后，才能读取最终轮廓。
        for i < len(events) && events[i][0] == x {
            height := events[i][1]
            if height < 0 {
                height = -height
                heightCount[height]++
                heap.Push(heights, height)
            } else {
                heightCount[height]--
            }
            i++
        }

        // 堆中可能残留失效高度，读最大值前清理零计数堆顶。
        for heightCount[(*heights)[0]] == 0 {
            heap.Pop(heights)
        }
        currentHeight := (*heights)[0]
        if currentHeight != previousHeight {
            result = append(result, []int{
                x,
                currentHeight,
            })
            previousHeight = currentHeight
        }
    }

    return result
}

复杂度分析

设建筑数量为 n，一共有 2n 个事件。

时间复杂度：$O(n\log(n+1))$。事件排序和高度维护占主导；Go 中每份高度记录只入堆一次、至多出堆一次，延迟清理的总次数仍为 $O(n)$。

空间复杂度：$O(n)$，用于事件数组、高度结构和关键点结果。

关键点总结

[!green]

左右边界之间覆盖集合不变，只需在端点更新最高高度。

同一横坐标先完成全部事件，再判断一次轮廓变化，无需为同坐标事件额外规定先后顺序。

等高建筑用次数区分，结束一栋不代表这个高度已经全部消失。

Go 的计数表代表真实有效性，堆只提供最高候选，读取前必须清理失效堆顶。

易错点总结

[!yellow]

每处理一个事件就输出：同一位置开始和结束的建筑可能互相抵消，会产生不存在的中间转折。

结束一栋就删除整个高度：其他仍在覆盖当前位置的等高建筑会被误删。

结束事件直接弹出最大堆顶：结束的建筑可能不是当前最高者，不能按堆顶位置删除它。

不清理失效堆顶：已结束的高楼会继续遮挡真正的轮廓。

每个端点都输出：有些端点不会改变最高高度，应只记录高度变化。

右边界延迟到下一个整数位置处理：建筑覆盖在右边界已经结束，不能把轮廓向右多延长一格。

相似题目

题目	难度	关联与区别
732. 我的日程安排表 III	困难	同样扫描区间起止事件，原题维护重叠数量，本题维护当前最高建筑高度。
699. 掉落的方块	困难	同样需要动态查询区间上的最大高度，原题新方块高度依赖此前覆盖，本题建筑高度预先固定。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2021/70275167

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！