题目

LeetCode.218.天际线问题（困难）

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

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

lefti 是第 i 座建筑物左边缘的 x 坐标。
righti 是第 i 座建筑物右边缘的 x 坐标。
heighti 是第 i 座建筑物的高度。
天际线应该表示为由 “关键点” 组成的列表，格式 [[x1,y1],[x2,y2],…] ，并按 x 坐标进行排序。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y 坐标始终为 0 ，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

注意：输出天际线中不得有连续的相同高度的水平线。例如 […[2 3], [4 5], [7 5], [11 5], [12 7]…] 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[…[2 3], [4 5], [12 7], …]

题解

思路

模拟一遍天际线形成的过程。
从简单的情况出发，逐步添加条件讨论复杂的情况。
穷举所有可能性，发现和总结重复的规律。

天际线受哪几个因素影响？

建筑物左边界和右边界
建筑物高度
建筑物个数

只有一个建筑时，天际线的关键点是哪些？

天际线的形成就是从左到右扫描建筑边界。

发现第一个建筑后，边际线的第一个关键点是第一个建筑左上角点。
后面没有其他建筑，边际线的第二个关键点是第一个建筑右下角点。

此时看不出来什么规律。

有两个建筑时，天际线的关键点受到怎样的影响？

为方便描述，先假设：
第一个建筑为A，下一个建筑为B，leftB > leftA。

leftB、rightB、heightB的变化都会影响天际线的变化，所以就分类讨论。

先看建筑B在横轴变化，再看高度变化：

B和A没有重叠（leftB > rightA）

此时B跟A的情况是一样的。

B和A有一部分重叠（leftB < rightA）

B的高度 > A的高度

B的左边界会影响天际线，天际线第2个关键点是B的左上角点（leftB, heightB）。

扩展：建筑横轴坐标不变，高度和个数变化

如果有很多不同高的建筑，边界横轴坐标都是leftB，应该选哪个建筑的边界为天际线？选最高的。

B的高度 < A的高度

B的左边界不会影响天际线。

如果rightB < rightA，B的右边界对天际线也没有影响。
如果rightB > rightA，天际线第2个关键点坐标是（rightA, heightB）。

扩展：建筑横轴坐标不变，高度和个数变化

如果有很多不同高的建筑，左右边界都在rightB两侧，应该选哪个建筑的边界为天际线？
选第二高的，因为最高的建筑到头了，只能选次高的做边际线。

规律

从左到右扫描

边际线增高的时候，关键点都是建筑左上角点，并且是相同左边界中最高的。
边际线降低的时候，关键点需要知道建筑右上角点横坐标，以及此横坐标下次高的建筑高度。

怎么获得建筑右上角点下面次高的建筑高度？
次高的建筑的左边在之前肯定扫描过了，所以可记录下建筑的高度。

也就是要保存所有建筑的左上角点的横坐标和高度、右上角点点横坐标和高度，并且要排序，才能知道哪个是最高哪个是次高。
排序还要在线排序才行，不能用离线排序算法，所以用优先队列来存储建筑的点，按高度排序，构建最大堆。

遍历到建筑左上角的点，要么在边际线增高的时候用到，要么在边际线递减的时候用来获得次高的高度，所以左上角点存储后需要保留。

遍历到建筑右上角点，边际线就向右延展结束了，就没有用了，我们需要获得次高的建筑高度，就需要把处在边际线高度的建筑的右上角点从优先队列中去除，这样就可以获得右边界下次高建筑的高度了。

所以优先队列记录的高度还需要区分是建筑的左上角点和右上角点，这里可以用负数表示左上角点的高度，正数表示右上角点的高度。

import java.util.*
import kotlin.Comparator

class Solution {

    data class Point(val x: Int, val y: Int)

    fun getSkyline(buildings: Array<IntArray>): List<List<Int>> {
        val answer = mutableListOf<List<Int>>()
        // 建筑物的左上角、右上角顶点坐标提取出来并按横坐标从小到大的排序
        val points = buildings.toSortedPoints()
        // 创建大顶堆，用以保存从左向右扫描的高度
        val queue = PriorityQueue<Int>(compareByDescending { it })
        // 初始插入0
        queue.offer(0)
        // 记录先前的天际线高度，如果高度发生变化了说明天际线发生了转折，需要记录
        // 因为有可能有几个高度一样的建筑物重叠在一起
        var preMax = 0
        points.forEach { p ->
            // 遇到左上角顶点，就将该顶点的高度插入最大堆，插入只需要对数时间
            if (p.y < 0) queue.offer(-p.y)
            // 遇到右上角顶点，就将该顶点高度从最大堆种删除，因为这个建筑不再影响天际线
            // 设堆中有n个元素，从堆中移除，首先需要找到这个元素，最坏需要耗费O(n)时间，与最后一个元素替换当作删除后再调整堆最坏需要耗费O(logn)时间
            else queue.remove(p.y)
            // 当前堆顶最大的高度，也就是天际线经过的高度
            val max = queue.peek()
            // 天际线高度发生了转折变化
            if (preMax != max) {
                // 添加天际线转折点坐标
                answer.add(listOf(p.x, max))
                // 记录这次的最大高度
                preMax = max
            }
        }
        return answer
    }

    /*
    求出每个建筑左上角和右上角坐标（横坐标,高度）, 并按横坐标从小到大的顺序排序
    当横坐标x相等时，该怎么排序，分以下三种情况:
    1. 两个坐标都是左上角的坐标，需要把较高的排在前面
    2. 两个坐标都是右上角的坐标，需要把较低的排在前面
    3. 一个坐标是左上角，另一个坐标是右上角，左上角需要排在前面
    上述判断起来比较麻烦，如果把左上角的高度存储为负数，上述三种情况只需要简单的按高度升序排序就可以达成效果
    同时也可以通过高度的正负来判定哪个是左上角的坐标哪个是右上角的
    */
    private fun Array<IntArray>.toSortedPoints(): List<Point> {
        return flatMap { building ->
            val leftX = building[0]
            val rightX = building[1]
            val height = building[2]
            listOf(
                    Point(leftX, -height),
                    Point(rightX, height)
            )
        }.sortedWith(Comparator { a, b -> if (a.x != b.x) a.x - b.x else a.y - b.y })
    }
}