LeetCode-每日一题 352. 将数据流变为多个不相交区间 [Java实现]

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

实现 SummaryRanges 类：

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

示例：

输入：
["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]]

        分析输出可得，对于每次添加数值，我们都应将其排序，为了更小的时间复杂度，此处们选取 TreeSet 这一数据结构来保证输出有序。

        我们可以初始化一个左端点值，因为区间连续仅可能是左右端点值差值为1（且 TreeSet 为我们避免了重复输入的情况），故在发现不连续区间（差值不唯一）时我们添加记录的左端点值和当前端点值，其即为一个符合题意的区间，并更新左端点值为下一个枚举项（注意此处要有临界判断）。

class SummaryRanges {
        private final TreeSet tree = new TreeSet<>();

        public void addNum(int val) {
            tree.add(val);
        }

        public int[][] getIntervals() {
            ArrayList result = new ArrayList<>(1 << 2);
            Iterator iterator = tree.iterator();
            int[] array = new int[tree.size()];
            int i = 0;
            while (iterator.hasNext()) array[i ++] = iterator.next();
            int length = array.length;
            if (length == 0) return result.toArray(new int[0][]);
            int start = array[0];

            for (i = 0; i < length; ++ i) {
                if (i+1 < length && array[i+1] - array[i] != 1) {
                    result.add(new int[] {start, array[i]});
                    start = array[i+1];
                } else if (i+1 == length) { // 处理右端点临界
                    result.add(new int[] {start, array[i]});
                }
            }

            return result.toArray(new int[result.size()][]);
        }

    }