跳转至

2762. 不间断子数组

题目描述

给你一个下标从 0 开始的整数数组 nums 。nums 的一个子数组如果满足以下条件，那么它是 不间断 的：

  • i，i + 1 ，...，j  表示子数组中的下标。对于所有满足 i <= i1, i2 <= j 的下标对，都有 0 <= |nums[i1] - nums[i2]| <= 2 。

请你返回 不间断 子数组的总数目。

子数组是一个数组中一段连续 非空 的元素序列。

 

示例 1：

输入：nums = [5,4,2,4]
输出：8
解释：
大小为 1 的不间断子数组：[5], [4], [2], [4] 。
大小为 2 的不间断子数组：[5,4], [4,2], [2,4] 。
大小为 3 的不间断子数组：[4,2,4] 。
没有大小为 4 的不间断子数组。
不间断子数组的总数目为 4 + 3 + 1 = 8 。
除了这些以外，没有别的不间断子数组。

示例 2：

输入：nums = [1,2,3]
输出：6
解释：
大小为 1 的不间断子数组：[1], [2], [3] 。
大小为 2 的不间断子数组：[1,2], [2,3] 。
大小为 3 的不间断子数组：[1,2,3] 。
不间断子数组的总数目为 3 + 2 + 1 = 6 。

 

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

解法

方法一：有序列表 + 双指针

我们可以用双指针 $i$ 和 $j$ 维护当前子数组的左右端点，用一个有序列表维护当前子数组的所有元素。

遍历数组 $nums$，对于当前遍历到的数字 $nums[i]$，我们将其加到有序列表中，如果此时有序列表中的最大值与最小值的差值大于 $2$，那么我们循环右移指针 $i$，不断将 $nums[i]$ 从有序列表中移出，直到列表为空或者有序列表元素的最大差值不大于 $2$。此时不间断的子数组数目为 $j - i + 1$，我们将其添加到答案中。

遍历结束，返回答案即可。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 $nums$ 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
from sortedcontainers import SortedList


class Solution:
    def continuousSubarrays(self, nums: List[int]) -> int:
        ans = i = 0
        sl = SortedList()
        for x in nums:
            sl.add(x)
            while sl[-1] - sl[0] > 2:
                sl.remove(nums[i])
                i += 1
            ans += len(sl)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public long continuousSubarrays(int[] nums) {
        long ans = 0;
        int i = 0, n = nums.length;
        TreeMap<Integer, Integer> tm = new TreeMap<>();
        for (int j = 0; j < n; ++j) {
            tm.merge(nums[j], 1, Integer::sum);
            while (tm.lastEntry().getKey() - tm.firstEntry().getKey() > 2) {
                tm.merge(nums[i], -1, Integer::sum);
                if (tm.get(nums[i]) == 0) {
                    tm.remove(nums[i]);
                }
                ++i;
            }
            ans += j - i + 1;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
        long long ans = 0;
        int i = 0, n = nums.size();
        multiset<int> s;
        for (int j = 0; j < n; ++j) {
            s.insert(nums[j]);
            while (*s.rbegin() - *s.begin() > 2) {
                s.erase(s.find(nums[i++]));
            }
            ans += j - i + 1;
        }
        return ans;
    }
};

 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
func continuousSubarrays(nums []int) (ans int64) {
    i := 0
    tm := treemap.NewWithIntComparator()
    for j, x := range nums {
        if v, ok := tm.Get(x); ok {
            tm.Put(x, v.(int)+1)
        } else {
            tm.Put(x, 1)
        }
        for {
            a, _ := tm.Min()
            b, _ := tm.Max()
            if b.(int)-a.(int) > 2 {
                if v, _ := tm.Get(nums[i]); v.(int) == 1 {
                    tm.Remove(nums[i])
                } else {
                    tm.Put(nums[i], v.(int)-1)
                }
                i++
            } else {
                break
            }
        }
        ans += int64(j - i + 1)
    }
}

方法二：单调队列 + 双指针

 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
function continuousSubarrays(nums: number[]): number {
    const [minQ, maxQ]: [number[], number[]] = [[], []];
    const n = nums.length;
    let res = 0;

    for (let r = 0, l = 0; r < n; r++) {
        const x = nums[r];
        while (minQ.length && nums[minQ.at(-1)!] > x) minQ.pop();
        while (maxQ.length && nums[maxQ.at(-1)!] < x) maxQ.pop();
        minQ.push(r);
        maxQ.push(r);

        while (minQ.length && maxQ.length && nums[maxQ[0]] - nums[minQ[0]] > 2) {
            if (maxQ[0] < minQ[0]) {
                l = maxQ[0] + 1;
                maxQ.shift();
            } else {
                l = minQ[0] + 1;
                minQ.shift();
            }
        }

        res += r - l + 1;
    }

    return res;
}

 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
function continuousSubarrays(nums) {
    const [minQ, maxQ] = [[], []];
    const n = nums.length;
    let res = 0;

    for (let r = 0, l = 0; r < n; r++) {
        const x = nums[r];
        while (minQ.length && nums[minQ.at(-1)] > x) minQ.pop();
        while (maxQ.length && nums[maxQ.at(-1)] < x) maxQ.pop();
        minQ.push(r);
        maxQ.push(r);

        while (minQ.length && maxQ.length && nums[maxQ[0]] - nums[minQ[0]] > 2) {
            if (maxQ[0] < minQ[0]) {
                l = maxQ[0] + 1;
                maxQ.shift();
            } else {
                l = minQ[0] + 1;
                minQ.shift();
            }
        }

        res += r - l + 1;
    }

    return res;
}

评论