352. Data Stream as Disjoint Intervals

Hard

Description

設計一個資料結構，接收整數串流並以不相交區間的形式總結目前收到的數字。實作 addNum(int value) 和 getIntervals() 兩個方法。

Example:

Input: addNum(1), addNum(3), addNum(7), addNum(2), addNum(6) getIntervals() -> [[1,3],[6,7]]

Intuition#

核心思路：用 TreeMap 維護區間集合，每次新增數字時檢查是否能與相鄰區間合併。

需要高效地找到新數字附近的區間——TreeMap 的 floorKey 和 higherKey 正好適合
新增一個值時有四種情況：
1. 獨立成新區間
2. 合併到左邊區間
3. 合併到右邊區間
4. 橋接左右兩個區間

Approaches#

1: TreeSet + 每次重建#

概念: 用 TreeSet 存所有數字，getIntervals 時掃描連續段
時間複雜度: addNum O(log n)、getIntervals O(n)
空間複雜度: O(n)

class SummaryRanges() {

    private val nums = TreeSet<Int>()

    fun addNum(value: Int) {
        nums.add(value)
    }

    fun getIntervals(): Array<IntArray> {
        if (nums.isEmpty()) return emptyArray()
        val result = mutableListOf<IntArray>()
        var start = -1
        var end = -1
        for (num in nums) {
            if (start == -1) {
                start = num
                end = num
            } else if (num == end + 1) {
                end = num
            } else {
                result.add(intArrayOf(start, end))
                start = num
                end = num
            }
        }
        result.add(intArrayOf(start, end))
        return result.toTypedArray()
    }
}

⭐2: TreeMap 維護區間#

概念: TreeMap 的 key 是區間起點、value 是區間終點。新增數字時用 floorKey/higherKey 找相鄰區間並合併
時間複雜度: addNum O(log n)、getIntervals O(n)
空間複雜度: O(n) - n 為不相交區間數量

class SummaryRanges() {

    // key = 區間起點, value = 區間終點
    private val intervals = TreeMap<Int, Int>()

    fun addNum(value: Int) {
        // 已存在於某區間中
        val lo = intervals.floorKey(value)
        val hi = intervals.higherKey(value)

        if (lo != null && intervals[lo]!! >= value) {
            // value 已被 [lo, intervals[lo]] 覆蓋
            return
        }

        val mergeLeft = lo != null && intervals[lo]!! + 1 == value
        val mergeRight = hi != null && hi == value + 1

        if (mergeLeft && mergeRight) {
            // 橋接左右區間
            intervals[lo] = intervals[hi]!!
            intervals.remove(hi)
        } else if (mergeLeft) {
            // 擴展左區間
            intervals[lo] = value
        } else if (mergeRight) {
            // 擴展右區間（需要更新 key）
            intervals[value] = intervals[hi]!!
            intervals.remove(hi)
        } else {
            // 獨立新區間
            intervals[value] = value
        }
    }

    fun getIntervals(): Array<IntArray> {
        return intervals.entries.map { intArrayOf(it.key, it.value) }.toTypedArray()
    }
}

🔑 Takeaways#

Pattern: TreeMap 維護有序區間集——用 floorKey/higherKey 高效定位相鄰區間
關鍵技巧: 新增數字時的四種合併情況（獨立、左擴、右擴、橋接）是區間合併問題的通用模式