LeetCode 352. 将数据流变为多个不相交区间（区间）

本文主要是介绍LeetCode 352. 将数据流变为多个不相交区间（区间），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给你一个由非负整数 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]]

提示：

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

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

思路：
一开始用的是list<pair<int,int>>lis来存，这样的话不能用二分，每次要通过遍历整个链表来维护区间关系。看了题解才发现，原来还可以用map来维护这个区间关系，太妙了。key表示左端点，value表示右端点。

将区间按照左端点排序（正好符合map排序规则）情况分为以下几种：

1. val在最左边区间左边，可能是单独区间，也可能和最左区间合并
2. val在某个区间之内
3. val在两个区间之间，而且刚好挨着前一个区间右端点，可能出现左右区间合并的情况
4. val在两个区间之间，而且刚好挨着后一个区间左端点，因为区间合并上面判过，这里无需再判
5. val在两个区间之间，没有上述情况，所以作为一个单独区间

可以加一个[1e9,1e9]作为dummy区间，省去很多判断的麻烦

class SummaryRanges {
public:SummaryRanges() {mp[1e9] = 1e9;}void addNum(int val) {auto interval1 = mp.upper_bound(val);auto interval0 = (interval1 == mp.begin() ? mp.end() : prev(interval1));if(interval0 == mp.end()) {if(val == interval1 -> first - 1) {mp[val] = interval1 -> second;mp.erase(interval1);} else {mp[val] = val;}return;}if(val <= interval0 -> second && val >= interval0 -> first) {return;}if(val == interval0 -> second + 1) {interval0 -> second++;if(interval0 -> second == interval1 -> first - 1) {interval0 -> second = interval1 -> second;mp.erase(interval1);}} else if(val == interval1 -> first - 1) {mp[val] = interval1 -> second;mp.erase(interval1);} else {mp[val] = val;}}vector<vector<int>> getIntervals() {vector<vector<int>>ans;for(auto& it: mp) {if(it.first == 1e9) continue;ans.push_back({it.first, it.second});}return ans;}
private:map<int, int>mp;
};/*** Your SummaryRanges object will be instantiated and called as such:* SummaryRanges* obj = new SummaryRanges();* obj->addNum(val);* vector<vector<int>> param_2 = obj->getIntervals();*/

这篇关于LeetCode 352. 将数据流变为多个不相交区间（区间）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---