題目描述:給定 n 棟建築,每棟以 [left, right, height] 表示。返回所有建築合併後天際線的關鍵點列表,每個關鍵點為 [x, height],表示在 x 位置天際線高度開始改變。
解題思路:使用掃描線(Line Sweep)演算法。將每棟建築分解為兩個事件:起始事件 (left, -height)(高度取負表示「進入」)和終止事件 (right, height)。將所有事件排序,優先按 x 坐標,x 相同時先處理高度較大的進入事件(避免在邊界誤產生點)。用一個 multiset 維護當前「活躍」的建築高度,初始放入哨兵高度 0。掃描每個事件:若為進入事件則插入高度;若為退出事件則移除一個對應高度。每次事件處理後,若 multiset 最大值(rbegin)改變,則記錄關鍵點 [x, newMaxH]。
時間複雜度:O(n² ) 最壞情況(multiset 的 erase + rbegin 均 O(log n),總共 2n 個事件故 O(n log n)),整體為 O(n log n)。
空間複雜度:O(n) — multiset 最多同時存 n 個活躍建築高度,事件陣列亦為 O(n)。
1. For each building [L, R, H], create two events: (L, -H) and (R, +H).
2. Sort events by x; on tie, process more-negative h first (start before end, taller before shorter).
3. Initialize activeHeights multiset with sentinel {0}; prevMax = 0.
4. For each event (x, h):
a. If h < 0: insert -h into activeHeights (building starts).
b. If h > 0: erase one occurrence of h from activeHeights (building ends).
c. curMax = max element of activeHeights.
d. If curMax != prevMax: append [x, curMax] to result; prevMax = curMax.
5. Return result.方法一:掃描線 + multiset(本題主解)O(n log n) 將建築拆成起止事件,用 multiset 維護活躍高度集合,rbegin() 取最大值。排序事件 O(n log n),每次插入/刪除 O(log n),共 2n 次,總體 O(n log n)。
方法二:分治合併 O(n log n) 類似合併排序,將建築列表分成左右兩半分別求天際線,再 O(n) 合併兩段天際線(雙指標掃描,維護各自當前最高)。程式碼較長但思路清晰,同樣 O(n log n)。
方法三:差分陣列 / 座標壓縮 + 線段樹 O(n log n) 將所有 x 座標壓縮,用線段樹或 BIT 支援區間更新與最大值查詢。適合動態加入建築的變體,但靜態問題中實作比 multiset 方法複雜。