HardRating 1700

352. Data Stream as Disjoint Intervals

binary-searchdesignordered-set

在 LeetCode 上作答 ↗

解題說明

Data Stream as Disjoint Intervals

題目描述：設計一個 SummaryRanges 類別，支援兩個操作：addNum(val) 將整數 val 加入資料流；getIntervals() 回傳所有不相交的閉合區間（升序排列），涵蓋目前資料流中所有數字。

解題思路：使用 std::map<int,int> intervals，以區間起點（start）為 key，終點（end）為 value，維護所有不相交區間集合。

addNum(val) 執行步驟：

先檢查 val 是否已在某個現有區間內，若是則直接返回（避免重複處理）。
找右鄰：auto right = intervals.lower_bound(val)——第一個 start ≥ val 的區間。
找左鄰：若 right != begin()，則 left = prev(right)——start < val 的最近區間。
判斷是否可與左鄰合併：若 left->second >= val - 1，表示左鄰的 end ≥ val-1，新數字緊貼或重疊左鄰。
判斷是否可與右鄰合併：若 right->first <= val + 1，表示右鄰的 start ≤ val+1，新數字緊貼或重疊右鄰。
根據以上判斷做四種情況處理：僅左合併、僅右合併、左右都合併（三者連成一個大區間）、無合併（插入新的單點區間 [val, val]）。

C++ 解法

複雜度分析

時間複雜度：addNum — O(log n)，其中 n 為目前不相交區間數量（map 的 lower_bound 和 erase 均為 O(log n)）；getIntervals — O(k)，k 為區間數量。

空間複雜度：O(n) — map 儲存最多 n 個不相交區間（n 為加入的不同數字個數）。

虛擬碼

addNum(val):
  right = first interval with start >= val
  if left neighbor exists and left.end >= val: return (already covered)
  mergeLeft  = left neighbor exists AND left.end >= val - 1
  mergeRight = right exists AND right.start <= val + 1
  if mergeLeft AND mergeRight:
    left.end = max(left.end, right.end)
    erase right
  else if mergeLeft:
    left.end = max(left.end, val)
  else if mergeRight:
    newEnd = right.end; erase right; insert [val, newEnd]
  else:
    insert [val, val]

getIntervals():
  for each (start, end) in map:
    append [start, end] to result
  return result

其他解法

有序集合 + 二分搜尋（TreeSet）：在 Java 中可用 TreeSet 配合 floor/ceiling 操作，原理相同，但 C++ 的 std::map 已是此模式的最佳實踐。

排序陣列 + 每次 getIntervals 合併：每次 addNum 只將值塞入一個 unordered_set，每次 getIntervals 時取出所有值排序並線性合併。優點是 addNum 為 O(1)，缺點是 getIntervals 為 O(n log n)，適合寫多讀少的場景。

線段樹 / 二元索引樹（BIT）：在值域範圍固定（如 0～10⁴）時，可用線段樹維護覆蓋區間，addNum 和 getIntervals 均為 O(log V)，適合值域小但呼叫頻繁的場景。

延伸思考

若需支援 removeNum(val) 操作，std::map 的設計應如何修改？
若資料流中的數字值域極大（如 0～10⁹），但數字個數 n 很小，本解法效率如何？與值域壓縮法比較。
若 getIntervals 呼叫頻率遠低於 addNum，選擇哪種實作方式更好？請分析時間與空間的取捨。