0352. Data Stream as Disjoint Intervals
=======================================
题目信息
--------
:题号: 0352
:难度: Hard
:主题: 设计、有序区间、数据流、状态维护
:原题: `LeetCode 0352 `_
:重点: 重复加入不改变结果、相邻整数合并为闭区间、区间按起点升序返回、对象跨调用保存状态
题目重述
--------
实现 ``SummaryRanges`` 数据结构。``addNum(value)`` 把一个非负整数加入数据流;``getIntervals()`` 返回当前已经加入的所有不同整数所组成的若干闭区间 ``[start, end]``。
返回的区间必须互不重叠、彼此不相邻,并按 ``start`` 严格升序排列。若某个整数被重复加入,已记录集合和区间结果都不发生变化。``value`` 位于 ``[0, 10^4]``,对对象的调用总数不超过 ``3 * 10^4``,其中 ``getIntervals`` 的调用次数不超过 ``100``。同一对象需要在连续调用之间保存已经接收的数据。
自建示例
--------
新值同时连接左右区间:
.. code-block:: text
调用:addNum(2), addNum(4), getIntervals(), addNum(3), getIntervals()
输出:[[2,2],[4,4]],随后为 [[2,4]]
解释:加入 3 之前,2 和 4 分属两个单点区间;3 同时与两侧相邻,因此三个整数合并成一个闭区间。
重复加入已有整数:
.. code-block:: text
调用:addNum(7), addNum(8), addNum(7), getIntervals()
输出:[[7,8]]
解释:第二次加入 7 不会产生重复元素,也不会改变现有区间。
有序区间只需检查左右两个邻居
------------------------------
用按起点排序的 ``map`` 保存当前互不相邻的区间。加入 ``value`` 时,``lower_bound`` 找到第一个起点不小于它的区间;它的前一个区间是唯一可能从左侧相邻或包含 ``value`` 的区间,当前找到的区间是唯一可能从右侧相邻的区间。因此只需判断“接左、接右、两边都接、两边都不接”四种情况。
若 ``value`` 已经落在左区间中,或恰好是右区间起点,直接返回;若左右都相邻,就把左区间的右端扩展到右区间的右端并删除右区间。只连接一侧时扩展对应端点,完全独立时插入单点区间。区间始终按起点排列,所以 ``getIntervals`` 只需顺序复制当前值。
C++ 实现
--------
.. code-block:: cpp
class SummaryRanges {
std::map intervals;
public:
SummaryRanges() = default;
void addNum(int value) {
auto right = intervals.lower_bound(value);
if (right != intervals.end() && right->first == value) {
return;
}
bool joinRight = right != intervals.end()
&& right->first == value + 1;
bool joinLeft = false;
auto left = right;
if (left != intervals.begin()) {
--left;
if (left->second >= value) return;
joinLeft = left->second == value - 1;
}
if (joinLeft && joinRight) {
left->second = right->second;
intervals.erase(right);
} else if (joinLeft) {
++left->second;
} else if (joinRight) {
int end = right->second;
intervals.erase(right);
intervals[value] = end;
} else {
intervals[value] = value;
}
}
std::vector> getIntervals() {
std::vector> result;
for (const auto& interval : intervals) {
result.push_back({interval.first, interval.second});
}
return result;
}
};
代码分析
--------
``map`` 的不变量是区间既不重叠也不相邻,因此一次加入最多合并两个已有区间;重复值会在落入左区间或撞上右端点时被忽略。每次 ``addNum`` 需要 ``O(log m)``,其中 ``m`` 是当前区间数;``getIntervals`` 按区间数 ``O(m)`` 输出,额外存储为 ``O(m)``。