LeetCode 218 The Skyline Problem：掃描線 + 最大堆

題目

給定建築物列表 [Li, Ri, Hi]，輸出天際線關鍵點 [[x1,y1],[x2,y2],...]。關鍵點為水平線段左端點，最後一點高度為 0。建築數 ≤ 10000。

掃描線算法

將每個建築拆為兩個事件：左邊 (Li, -Hi) 入堆，右邊 (Ri, Hi) 出堆。按 x 排序，x 相同時左邊優先（高度大優先），右邊高度小優先。掃描維護最大堆（當前活躍建築高度），堆頂變化時記錄關鍵點。用延遲刪除（懶惰標記）處理堆中過期元素。

代碼 (Java)

public List getSkyline(int[][] buildings) {
    List events = new ArrayList<>();
    for (int[] b : buildings) {
        events.add(new int[]{b[0], -b[2]}); // 入
        events.add(new int[]{b[1], b[2]});  // 出
    }
    events.sort((a,b) -> a[0]!=b[0] ? a[0]-b[0] : a[1]-b[1]); // 排序規則
    PriorityQueue pq = new PriorityQueue<>((a,b)->b-a); // 最大堆
    pq.offer(0);
    List res = new ArrayList<>();
    int prev = 0;
    for (int[] e : events) {
        if (e[1] < 0) pq.offer(-e[1]);
        else pq.remove(e[1]); // O(n) remove，實際用 Map 計數延遲刪除更優
        int cur = pq.peek();
        if (cur != prev) {
            res.add(new int[]{e[0], cur});
            prev = cur;
        }
    }
    return res;
}

優化說明

Java PriorityQueue.remove() 為 O(n)，大數據下需改用 TreeMap 或雙堆延遲刪除實現 O(log n) 刪除。C++ 可用 multiset。