题目描述
题目描述
给出一个非负整数的数据流 a1,a2,…an,…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]
map存储的是左右区间端点,每个区间端点会存2份(端点重合除外),也就是说通过map,左端点可以索引到右端点,右端点可以索引到左端点,[i,j],有map[i]=j;map[j]=i;
class SummaryRanges {
public:
/** Initialize your data structure here. */
map<int, int> m;
SummaryRanges() {
}
void addNum(int val) {
if(m.count(val)) return;//重复直接返回
m[val]=val;
int mn=val,mx=val;
if(m.count(val-1)) mn=m[val-1];//val-1存在更新左端点,m[val-1]索引到val-1所在区间的左端点
if(m.count(val+1)) mx=m[val+1];//val+1存在更新右端点
m[mx]=mn;
m[mn]=mx;
}
vector<vector<int>> getIntervals() {
vector<vector<int>>res;
int min_v=-1;
for(auto t:m)
if(t.first>min_v)//避免部分区间重复
{
res.push_back({t.first,t.second});
min_v=t.second;//记录区间右端点
}
return res;
}
};