2762.不间断子数组

链接：2762.不间断子数组
难度：Medium
标签：队列、数组、有序集合、滑动窗口、单调队列、堆（优先队列）
简介：给你一个下标从 0 开始的整数数组 nums 。请你返回 不间断 子数组的总数目。

题解 1 - cpp

• 编辑时间：2023-07-02
• 执行用时：1256ms
• 内存消耗：110.4MB
• 编程语言：cpp
• 解法介绍：平衡树。

struct Node {
    int idx, num;
    Node(int idx, int num): idx(idx), num(num) {}
    bool operator<(const Node &o) const {
        return num < o.num;
    }
};
class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
        int n = nums.size(), prev = 0;
        long long res = 1;
        multiset<Node> s;
        s.insert(Node(0, nums[0]));
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            if (s.size()) {
                auto it = s.begin();
                while (s.size() && abs(num - it->num) > 2) {
                    prev = max(prev, it->idx + 1);
                    s.erase(it++);
                }
            }
            if (s.size()) {
                auto it = s.end();
                it--;
                while (s.size() && abs(num - it->num) > 2) {
                    prev = max(prev, it->idx + 1);
                    s.erase(it--);
                }
            }
            s.insert(Node(i, num));
            res += i - prev + 1;
        }
        return res;
    }
};