給定一組建築
[left, right, height]，輸出天際線的關鍵轉折點[x, height]：每當「目前最高建築」的高度改變，就記錄一個點。
Example:
Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]] Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Intuition
TIP
核心思路：掃描線 + 最大堆。把每棟建築拆成「進入」與「離開」兩個事件，沿 x 由左到右掃；用最大堆維護當前所有覆蓋此處的建築高度，堆頂改變時就產生一個關鍵點。
- 事件排序：x 升序；同 x 時「進入」排在「離開」前、較高的先處理（避免漏點）
- 進入 → 高度入堆；離開 → 標記延遲刪除
- 每處理完一個 x，清掉堆頂已離開者，若堆頂高度 ≠ 前一次最高 → 記錄
[x, 新高]
Approaches
⭐ Sweep Line + Max Heap (lazy deletion) — O(n log n) / O(n)
- Idea: 事件驅動掃描，最大堆維護活躍高度，懶刪除離開的建築
- Time:
O(n log n)- 事件排序 + 堆操作 - Space:
O(n)- 事件、堆、刪除計數
import java.util.PriorityQueue
class Solution {
fun getSkyline(buildings: Array<IntArray>): List<List<Int>> {
val events = ArrayList<IntArray>()
for (b in buildings) {
events.add(intArrayOf(b[0], -b[2])) // 進入：負高度
events.add(intArrayOf(b[1], b[2])) // 離開：正高度
}
// x 升序；同 x 依高度值升序（進入(負)在前、較高先處理）
events.sortWith(compareBy({ it[0] }, { it[1] }))
val result = ArrayList<List<Int>>()
val heap = PriorityQueue<Int>(compareByDescending { it }) // 最大堆
heap.add(0)
val toRemove = HashMap<Int, Int>()
var prevMax = 0
for (e in events) {
val x = e[0]
if (e[1] < 0) {
heap.add(-e[1]) // 進入
} else {
toRemove[e[1]] = (toRemove[e[1]] ?: 0) + 1 // 離開：延遲刪除
}
while (heap.isNotEmpty() && (toRemove[heap.peek()] ?: 0) > 0) {
toRemove[heap.peek()] = toRemove[heap.peek()]!! - 1
heap.poll()
}
val curMax = heap.peek() ?: 0
if (curMax != prevMax) {
result.add(listOf(x, curMax))
prevMax = curMax
}
}
return result
}
}Note: Divide & Conquer
也可像歸併排序一樣分治：把建築分兩半各自求天際線，再「合併兩條天際線」（類似合併兩個有序序列，逐點取較高者）。同為 O(n log n)，合併階段是關鍵，思路接近 23 合併 K 條鏈結串列的合併概念。
🔑 Takeaways
- Pattern: 掃描線 + 最大堆（延遲刪除）——處理「區間覆蓋下的當前最值」
- Key trick: 事件排序的細節（同 x 進入在前、較高先處理）決定正確性；堆無法 O(1) 刪任意元素，用「計數延遲刪除、只在堆頂清理」繞過。與 253 會議室 II 同屬掃描線家族