破題

這題是一個經典的幾何問題。給定一個建築物列表，每個建築物由其左邊界、右邊界和高度表示，我們需要找出這些建築物形成的天際線。天際線是由水平線段組成的，這些線段表示從一個建築物的頂部到另一個建築物的頂部的視線。

跟一流的人才幹大事，享受成功進步的高級樂趣！
內推機會來啦！能與優秀的程式設計師共事，是特別痛快的事，因為厲害的工程師大神會刺激你想要迎頭趕上的上進心，尤其是一起討論解決方案時，他們會觸發你有更好的解決思維能力，彼此共同成長並且一起享受解謎與破關般的樂趣。 你一定聽得懂我在說甚麼感覺，趕快把握機會，動動手指投遞履歷吧！ 立即加入「面試讀書會」，和大家一起準備面試！

內推機會	加入讀書會 (邀請碼：6685)

解題思路

這個解法的主要思路是將每個建築物分解為兩個事件：開始和結束。對於每個事件，我們都記錄其相應的高度。對於開始事件，高度為正數，對於結束事件，高度為負數。然後，我們按時間順序處理所有事件，並使用一個資料結構（在此解法中是一個 List）來追蹤目前的建築物。當我們遇到一個開始事件時，我們將它加到 List 中。當我們遇到一個結束事件時，我們從 List 中移除它。在處理每個事件時，我們都檢查 List 的最大高度是否改變。如果有，則將其添加到 result 中。

程式

import java.lang.Integer.max
class Solution {
    fun getSkyline(buildings: Array<IntArray>): List<List<Int>> {
        var maxIndex = 0
        buildings.forEach { building ->
            if (building[0] > maxIndex) maxIndex = building[0]
            if (building[1] > maxIndex) maxIndex = building[1]
        }

        val intArray = mutableMapOf<Int, List<Int>>()

        buildings.forEach { building ->
            val height = building[2]
            intArray[building[0]] = intArray.getOrDefault(building[0], listOf()).toMutableList().apply {
                add(height)
            }
            intArray[building[1]] = intArray.getOrDefault(building[1], listOf()).toMutableList().apply {
                add(-height)
            }
        }

        val result = mutableListOf<List<Int>>()
        var prevSet = mutableListOf<Int>()
        var height = 0

        intArray.toSortedMap().forEach { (index, set) ->
            val minus = set.filter { it < 0 }.map { -it }
            val plus = set.filter { it > 0 }
            val nextSet = if (index > 0) prevSet.apply {
                minus.forEach { remove(it) }
                addAll(plus)
            } else set
            val nextHeight = nextSet.max() ?: 0
            if (height != nextHeight) {
                result.add(listOf(index, nextHeight))
            }
            prevSet = nextSet.toMutableList()
            height = nextHeight
        }

        return result
    }
}

複雜度分析

• 時間複雜度:
  ，其中 是建築物的數量。這是因為我們需要對所有的事件（開始和結束）進行排序，並且對於每個事件，我們可能需要更新 List。

• 空間複雜度:
  ，我們需要存儲所有的事件以及作為暫存的 List。

　更多 LeetCode 解答在此，一起來學習！

內推機會來啦！

跟一流的人才幹大事，享受成功進步的高級樂趣！

內推機會	加入讀書會 (邀請碼：6685)