题目描述 给定一个非负整数的数据流输入 a1，a2，…，an，…，将到目前为止看到的数字总结为不相交的区间列表。 例如，假设数据流中的整数为 1，3，7，2，6，…，每次的总结为： [1, 1] [1, 1], [3, 3] [1, 1], [3, 3], [7, 7] [1, 3], [7, 7] [1, 3], [6, 7] 进阶：如果有很多合并，并且与数据流的大小相比，不相交区间的数量很小，该怎么办? 提示：特别感谢 @yunhong 提供了本问题和其测试用例。 https://leetcode-cn.com/problems/data-stream-as-disjoint-intervals/ 解法1 这道题我们使用TreeMap来解决。TreeMap的底层实现是R-B Tree，它的平衡性很好，对于get、put、remove、contains等操作都能够达到O(logn)的时间复杂度。我们使用的TreeMap的Key为插入操作的值，Value为能够表示插入值的最小区间。例如，我们向map中插入2，用[2,2]能够表示，用[1,3]能够表示，用[-1000,1000]也能够表示，但是我们选择最小的区间[2, 2]，这样做能做到题目要求的“目前为止看到的数字总结为不相交的区间列表“。 这里我们还用到了TreeMap提供的两个重要的操作floorEntry与ceilingEntry。floorEntry(k)返回小于等于k的最大元组；ceilingEntry(k)返回大于等于k的最小元组。我们记leftValInterval = map.floorEntry(val)，rightValInterval = map.ceilingEntry(val)。 我们将插入的值与区间已有的值的关系分为图1的6种情况。case1、case3、case5表示已有的区间能够表示插入的值，其实case5能够和case1或case3合并。case2与case4表示插入值与已有的区间连续，那么将已有的区间扩大一个单元就能够表示插入值，例如向[1, 3]插入4，向[3, 4]插入2。case6表示如果有了插入值，就能够使得已有的左右区间连续，例如向[1, 4]和[6, 9]插入5。 如果我们清晰的分析出来这些情况，编写代码就不难了。对于新插入的值val，我们首先判断他们在TreeMap中是否存在，如果存在则返回。否则，查询val的floorEntry与ceilingEntry。如果floorEntry的右边界等于val-1，就说明我们可以将val合并到floorEntry对应的区间，将区间扩大，如图1中case2所示。对于ceilingEntry的处理同理，如图1中case4所示。如果floorEntry的右边界等于val-1且ceilingEntry的左边界等于val+1，说明我们将val插入到这两个区间后，能够使得这两个区间连续，如图1中case6所示。如果不满足图1中任何一个case，说明val无法被TreeMap中已有的区间无法表示，我们需要向TreeMap插入新区间[val, val]。 全部代码如下所示，时间复杂度O(nlogn)，空间复杂度O(n)。