LeetCode 第352题：将数据流变为多个不相交区间

📖 文章摘要

本文详细解析LeetCode第352题“将数据流变为多个不相交区间”，这是一道考察有序集合和区间合并的中等难度题目。文章提供了基于TreeMap的解法，包含C#、Java、Python三种语言实现，配有详细的思路分析和性能对比。适合想要深入理解数据结构和区间操作的程序员。

核心知识点： 有序集合、区间合并、数据流处理
难度等级： 中等
推荐人群： 数据结构进阶学习者、面试备考者

题目描述

给你一个由非负整数 a1, a2, ..., an 组成的数据流输入，请你将到目前为止看到的数字总结为不相交的区间列表。

实现 SummaryRanges 类：

• SummaryRanges() 使用一个空数据流初始化对象
• void addNum(int val) 向数据流中加入整数 val
• int[][] getIntervals() 以不相交区间 [starti, endi] 的列表形式返回对数据流中整数的总结

示例

示例 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]]]

解释：
SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.addNum(1);      // arr = [1]
summaryRanges.getIntervals(); // 返回 [[1, 1]]
summaryRanges.addNum(3);      // arr = [1, 3]
summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3]]
summaryRanges.addNum(7);      // arr = [1, 3, 7]
summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3], [7, 7]]
summaryRanges.addNum(2);      // arr = [1, 2, 3, 7]
summaryRanges.getIntervals(); // 返回 [[1, 3], [7, 7]]
summaryRanges.addNum(6);      // arr = [1, 2, 3, 6, 7]
summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]

提示

• 0 <= val <= 104
• 最多调用 addNum 和 getIntervals 方法 3 * 104 次

解题思路

本题的核心是维护一个有序的区间集合，并在添加新数字时正确处理区间的合并。主要解法如下：

1. 使用有序集合（TreeMap）存储区间

   • 以区间的左边界为键
   • 以区间的右边界为值
   • 保证区间按左边界有序存储

2. 添加新数字时的处理逻辑：

   • 查找左侧最近的区间（floor）
   • 查找右侧最近的区间（ceiling）
   • 根据新数字与相邻区间的关系进行合并

3. 可能的情况分析：

   • 新数字在某个区间内：无需改变
   • 新数字与左区间相连：扩展左区间
   • 新数字与右区间相连：扩展右区间
   • 新数字连接左右区间：合并两个区间
   • 新数字独立于现有区间：创建新区间

代码实现

C# 实现

public class SummaryRanges {
    private SortedDictionary<int, int> intervals;

    public SummaryRanges() {
        intervals = new SortedDictionary<int, int>();
    }
    
    public void AddNum(int val) {
        // 如果值已存在于某个区间，直接返回
        if (intervals.Any(kv => kv.Key <= val && val <= kv.Value)) {
            return;
        }
        
        // 查找左右相邻区间
        var leftInterval = intervals
            .Where(kv => kv.Value + 1 == val)
            .Select(kv => kv)
            .FirstOrDefault();
            
        var rightInterval = intervals
            .Where(kv => kv.Key - 1 == val)
            .Select(kv => kv)
            .FirstOrDefault();
        
        if (leftInterval.Value != 0 && rightInterval.Value != 0) {
            // 可以连接左右区间
            int newStart = leftInterval.Key;
            int newEnd = rightInterval.Value;
            intervals.Remove(leftInterval.Key);
            intervals.Remove(rightInterval.Key);
            intervals.Add(newStart, newEnd);
        }
        else if (leftInterval.Value != 0) {
            // 可以连接左区间
            intervals.Remove(leftInterval.Key);
            intervals.Add(leftInterval.Key, val);
        }
        else if (rightInterval.Value != 0) {
            // 可以连接右区间
            intervals.Remove(rightInterval.Key);
            intervals.Add(val, rightInterval.Value);
        }
        else {
            // 创建新区间
            intervals.Add(val, val);
        }
    }
    
    public int[][] GetIntervals() {
        return intervals
            .Select(kv => new int[] { kv.Key, kv.Value })
            .ToArray();
    }
}

Java 实现

class SummaryRanges {
    private TreeMap<Integer, Integer> intervals;
    
    public SummaryRanges() {
        intervals = new TreeMap<>();
    }
    
    public void addNum(int val) {
        // 查找左侧最近的区间
        Integer leftKey = intervals.floorKey(val);
        if (leftKey != null && intervals.get(leftKey) >= val) {
            return; // 已在某个区间内
        }
        
        // 查找右侧最近的区间
        Integer rightKey = intervals.ceilingKey(val);
        
        // 判断是否可以与左区间合并
        boolean mergeLeft = leftKey != null && intervals.get(leftKey) + 1 == val;
        // 判断是否可以与右区间合并
        boolean mergeRight = rightKey != null && rightKey == val + 1;
        
        if (mergeLeft && mergeRight) {
            // 合并左右区间
            intervals.put(leftKey, intervals.get(rightKey));
            intervals.remove(rightKey);
        } else if (mergeLeft) {
            // 扩展左区间
            intervals.put(leftKey, val);
        } else if (mergeRight) {
            // 扩展右区间
            intervals.put(val, intervals.get(rightKey));
            intervals.remove(rightKey);
        } else {
            // 创建新区间
            intervals.put(val, val);
        }
    }
    
    public int[][] getIntervals() {
        int[][] result = new int[intervals.size()][2];
        int i = 0;
        for (Map.Entry<Integer, Integer> entry : intervals.entrySet()) {
            result[i][0] = entry.getKey();
            result[i][1] = entry.getValue();
            i++;
        }
        return result;
    }
}

Python 实现

from sortedcontainers import SortedDict

class SummaryRanges:
    def __init__(self):
        self.intervals = SortedDict()  # {start: end}
        
    def addNum(self, val: int) -> None:
        # 查找左侧最近的区间
        left_idx = self.intervals.bisect_right(val) - 1
        if left_idx >= 0 and self.intervals.peekitem(left_idx)[1] >= val:
            return  # 已在某个区间内
            
        left_merge = (left_idx >= 0 and 
                     self.intervals.peekitem(left_idx)[1] + 1 == val)
        
        # 查找右侧最近的区间
        right_idx = self.intervals.bisect_left(val)
        right_merge = (right_idx < len(self.intervals) and 
                      self.intervals.peekitem(right_idx)[0] == val + 1)
        
        if left_merge and right_merge:
            # 合并左右区间
            left_start = self.intervals.peekitem(left_idx)[0]
            right_end = self.intervals.peekitem(right_idx)[1]
            self.intervals.pop(self.intervals.peekitem(right_idx)[0])
            self.intervals[left_start] = right_end
        elif left_merge:
            # 扩展左区间
            self.intervals[self.intervals.peekitem(left_idx)[0]] = val
        elif right_merge:
            # 扩展右区间
            right_end = self.intervals.peekitem(right_idx)[1]
            self.intervals.pop(self.intervals.peekitem(right_idx)[0])
            self.intervals[val] = right_end
        else:
            # 创建新区间
            self.intervals[val] = val
            
    def getIntervals(self) -> List[List[int]]:
        return [[start, end] for start, end in self.intervals.items()]

复杂度分析

时间复杂度

• addNum: O(log n)，其中n是当前区间的数量
  • 查找左右相邻区间：O(log n)
  • 更新区间：O(log n)
• getIntervals: O(n)，需要遍历所有区间

空间复杂度

• O(n)，其中n是不相交区间的数量
• 每个数字最多贡献一个区间

代码亮点

1. 🎯 使用有序集合高效管理区间
2. 💡 巧妙处理区间合并的各种情况
3. 🔍 利用二分查找快速定位相邻区间
4. 🎨 代码结构清晰，易于维护

常见错误分析

1. 🚫 忘记处理区间合并的边界情况
2. 🚫 未正确处理重复数字
3. 🚫 区间更新时的并发修改问题
4. 🚫 未考虑数据流的连续性

相关题目

• LeetCode 56. 合并区间 - 中等
• LeetCode 57. 插入区间 - 中等
• LeetCode 228. 汇总区间 - 简单

解题技巧总结

1. 使用有序集合维护区间信息
2. 考虑所有可能的区间合并情况
3. 利用二分查找优化查找效率
4. 注意处理边界条件和特殊情况

---

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第352题。

---

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

• 👍 点个赞，让更多人看到这篇文章
• 📁 收藏文章，方便后续查阅复习
• 🔔 关注作者，获取更多高质量算法题解
• 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！