将数据流变为多个不相交区间

Posted on Edited on In Views: Waline: Views: Symbols count in article: 1.3k Reading time ≈ 1 mins.

题解方法

  • 有序映射

区间集合

  1. 存在区间[l, r]，满足l<= val<=r，无变化；
  2. 存在区间[l, r]，满足val=r+1，该区间变为[l, r+1]；
  3. 存在区间[l, r]，满足val=l-1，该区间变为[l-1, r]；
  4. 存在区间[l0, r0]、[l1, r1]，满足val=r0+1=l1-1，两区间合并为[l0, r1]；
  5. 以上均不满足，val单独成立新区间[val, val]。

有序映射

  • 键存放左区间，值存放右区间
  • 支持查询“最大的比某个元素小的键“与“最小的比某个元素大的键”

核心代码

区间查询

1
2
3
4
// 找到l1最小且满足l1>val的区间
Map.Entry<Integer, Integer> interval1 = intervals.ceilingEntry(val + 1);
// 找到l0最大且满足l0<=val的区间
Map.Entry<Integer, Integer> interval0 = intervals.floorEntry(val);

情况讨论

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 情况一
if (interval0 != null && interval0.getKey() <= val && val <= interval0.getValue()) {
    return;
}
else {
    boolean leftAside = interval0 != null && interval0.getValue() + 1 == val;
    boolean rightAside = interval1 != null && interval1.getKey() - 1 == val;
    // 情况四
    if (leftAside && rightAside) {
        int left = interval0.getKey(), right = interval1.getValue();
        intervals.remove(interval0.getKey());
        intervals.remove(interval1.getKey());
        intervals.put(left, right);
    }
    // 情况二
    else if (leftAside) {
        intervals.put(interval0.getKey(), val);
    }
    // 情况三
    else if (rightAside) {
        intervals.put(val, interval1.getValue());
        intervals.remove(interval1.getKey());
    } else {
        // 情况五
        intervals.put(val, val);
    }
}

题目来源

352. 将数据流变为多个不相交区间 - 力扣（LeetCode） (leetcode-cn.com)