352. 数据流的不相交区间

Hard

题目描述

给定一个非负整数数据流 a1, a2, …, an，将到目前为止看到的数字总结为一个不相交区间的列表。

实现 SummaryRanges 类：

SummaryRanges() 使用一个空数据流初始化对象。
void addNum(int value) 向数据流中添加整数 value。
int[][] getIntervals() 以不相交区间 [starti, endi] 的列表形式返回对数据流中整数的总结。答案应该按 starti 排序。

示例 1：

输入：
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
输出：
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]

提示：

0 <= value <= 10^4
最多调用 addNum 和 getIntervals 方法 3 * 10^4 次
最多调用 getIntervals 方法 10^2 次

进阶： 如果有大量的合并操作，并且与数据流大小相比，不相交区间的数量很小，该怎么办？

解题思路

这道题需要维护一个数据结构来存储不相交的区间，并能高效地插入新数字和查询所有区间。

核心思路： 使用 map 或有序集合维护区间集合，每个区间用起始位置作为键，结束位置作为值。

添加数字的处理逻辑：

检查新数字是否已存在，如果存在直接返回
查找新数字可能合并的区间：
- 左侧相邻区间：结束位置为 value-1 的区间
- 右侧相邻区间：开始位置为 value+1 的区间
根据合并情况处理：
- 无合并：创建新区间 [value, value]
- 与左侧合并：扩展左侧区间
- 与右侧合并：扩展右侧区间
- 与两侧合并：合并三个区间为一个

时间复杂度分析：

addNum: O(log n)，主要是 map 的查找和插入操作
getIntervals: O(n)，遍历所有区间

这种方法在区间数量较少时特别高效，因为我们只存储区间而不是所有数字。

代码实现

class SummaryRanges {
private:
    map<int, int> intervals; // start -> end
    
public:
    SummaryRanges() {
        
    }
    
    void addNum(int value) {
        // 检查是否已经在某个区间中
        auto it = intervals.upper_bound(value);
        if (it != intervals.begin()) {
            --it;
            if (it->second >= value) {
                return; // 已经在区间中
            }
        }
        
        // 检查左侧相邻区间
        auto left = intervals.find(value - 1);
        auto leftEnd = left != intervals.end() ? left->second : -1;
        
        // 检查右侧相邻区间
        auto right = intervals.find(value + 1);
        
        if (left != intervals.end() && right != intervals.end()) {
            // 合并左右两个区间
            intervals[left->first] = right->second;
            intervals.erase(right);
        } else if (left != intervals.end()) {
            // 扩展左侧区间
            intervals[left->first] = value;
        } else if (right != intervals.end()) {
            // 扩展右侧区间
            intervals[value] = right->second;
            intervals.erase(right);
        } else {
            // 创建新区间
            intervals[value] = value;
        }
    }
    
    vector<vector<int>> getIntervals() {
        vector<vector<int>> result;
        for (const auto& interval : intervals) {
            result.push_back({interval.first, interval.second});
        }
        return result;
    }
};

class SummaryRanges:

    def __init__(self):
        from sortedcontainers import SortedDict
        self.intervals = SortedDict()  # start -> end

    def addNum(self, value: int) -> None:
        # 检查是否已经在某个区间中
        idx = self.intervals.bisect_right(value)
        if idx > 0:
            start = self.intervals.peekitem(idx - 1)[0]
            end = self.intervals[start]
            if end >= value:
                return  # 已经在区间中
        
        # 检查左侧相邻区间
        left_start = value - 1
        left_end = self.intervals.get(left_start, -1)
        
        # 检查右侧相邻区间
        right_start = value + 1
        right_end = self.intervals.get(right_start, -1)
        
        if left_end != -1 and right_end != -1:
            # 合并左右两个区间
            self.intervals[left_start] = right_end
            del self.intervals[right_start]
        elif left_end != -1:
            # 扩展左侧区间
            self.intervals[left_start] = value
        elif right_end != -1:
            # 扩展右侧区间
            self.intervals[value] = right_end
            del self.intervals[right_start]
        else:
            # 创建新区间
            self.intervals[value] = value

    def getIntervals(self) -> list[list[int]]:
        return [[start, end] for start, end in self.intervals.items()]

public class SummaryRanges {
    private SortedDictionary<int, int> intervals; // start -> end

    public SummaryRanges() {
        intervals = new SortedDictionary<int, int>();
    }
    
    public void AddNum(int value) {
        // 检查是否已经在某个区间中
        var keys = intervals.Keys.Where(k => k <= value).ToList();
        if (keys.Count > 0) {
            int start = keys.Last();
            if (intervals[start] >= value) {
                return; // 已经在区间中
            }
        }
        
        // 检查左侧相邻区间
        bool hasLeft = intervals.ContainsKey(value - 1);
        int leftEnd = hasLeft ? intervals[value - 1] : -1;
        
        // 检查右侧相邻区间
        bool hasRight = intervals.ContainsKey(value + 1);
        int rightEnd = hasRight ? intervals[value + 1] : -1;
        
        if (hasLeft && hasRight) {
            // 合并左右两个区间
            intervals[value - 1] = rightEnd;
            intervals.Remove(value + 1);
        } else if (hasLeft) {
            // 扩展左侧区间
            intervals[value - 1] = value;
        } else if (hasRight) {
            // 扩展右侧区间
            intervals[value] = rightEnd;
            intervals.Remove(value + 1);
        } else {
            // 创建新区间
            intervals[value] = value;
        }
    }
    
    public int[][] GetIntervals() {
        var result = new int[intervals.Count][];
        int i = 0;
        foreach (var kvp in intervals) {
            result[i++] = new int[] { kvp.Key, kvp.Value };
        }
        return result;
    }
}

var SummaryRanges = function() {
    this.intervals = new Map(); // start -> end
};

SummaryRanges.prototype.addNum = function(value) {
    // 检查是否已经在某个区间中
    for (let [start, end] of this.intervals) {
        if (start <= value && value <= end) {
            return; // 已经在区间中
        }
    }
    
    // 检查左侧相邻区间
    const hasLeft = this.intervals.has(value - 1);
    const leftEnd = hasLeft ? this.intervals.get(value - 1) : -1;
    
    // 检查右侧相邻区间
    const hasRight = this.intervals.has(value + 1);
    const rightEnd = hasRight ? this.intervals.get(value + 1) : -1;
    
    if (hasLeft && hasRight) {
        // 合并左右两个区间
        this.intervals.set(value - 1, rightEnd);
        this.intervals.delete(value + 1);
    } else if (hasLeft) {
        // 扩展左侧区间
        this.intervals.set(value - 1, value);
    } else if (hasRight) {
        // 扩展右侧区间
        this.intervals.set(value, rightEnd);
        this.intervals.delete(value + 1);
    } else {
        // 创建新区间
        this.intervals.set(value, value);
    }
};

SummaryRanges.prototype.getIntervals = function() {
    const result = [];
    const sortedKeys = Array.from(this.intervals.keys()).sort((a, b) => a - b);
    
    for (const start of sortedKeys) {
        result.push([start, this.intervals.get(start)]);
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
addNum	O(log n)	O(1)
getIntervals	O(n)	O(n)

其中 n 是当前区间的数量。在最坏情况下，如果所有数字都不相邻，区间数量等于添加的数字数量。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目