不间断子数组

标签: 队列 数组 有序集合 滑动窗口 单调队列 堆（优先队列）

难度: Medium

给你一个下标从 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

Submission

运行时间: 133 ms

内存: 24.5 MB

class Solution:
    def continuousSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        if n > 1:
            i = 0
            while i < n:
                maxV = minV = [nums[i],i]
                s = 0
                for j in range(i+1,n):
                    if nums[j] >= maxV[0]:
                        maxV = [nums[j], j]
                    elif nums[j] <= minV[0]:
                        minV = [nums[j], j]
                    if maxV[0] - minV[0] > 2:
                        k = 1
                        while k <= j and abs(nums[j] - nums[j - k]) <= 2:
                            k += 1
                        else:
                            s = (j - i + 1) * (j - i) / 2 - (j - i) - (k * (k - 1) / 2 - k + 1)
                            i = j - k + 1
                            ans += s
                        break
                else:
                    ans += (j - i + 2) * (j - i + 1) / 2 - (j - i + 1)
                    break
        return int(ans + n)

Explain

该题解采用了一个双指针技术来确定符合条件的不间断子数组。指针i作为子数组的起始点，而指针j从i开始向后遍历，检查每个新元素是否能扩展当前的不间断子数组。为了判断是否满足不间断条件，算法维护了当前子数组中的最大值maxV和最小值minV，并更新这两个值随着j的增加。如果这两个值的差大于2，表明当前子数组已不再满足条件，因此计算到目前为止的所有可能子数组数目，并调整i的位置来尝试新的子数组。如果j到达数组末尾而没有超过范围，那么将当前子数组的计数加入最终结果中。此外，对于单个元素的子数组，最后结果需再加上n。

时间复杂度: O(n^2)

空间复杂度: O(1)

class Solution:
    def continuousSubarrays(self, nums: List[int]) -> int:
        n = len(nums)  # 数组的长度
        ans = 0  # 存储所有满足条件的子数组数量
        if n > 1:  # 如果数组长度大于1，才进行处理
            i = 0  # 初始化起始指针i
            while i < n:  # 当i小于数组长度时循环
                maxV = minV = [nums[i],i]  # 初始化最大值和最小值为起点i的元素
                s = 0  # 存储当前子数组计数
                for j in range(i+1,n):  # 从i+1开始，尝试扩展子数组
                    if nums[j] >= maxV[0]:  # 更新最大值
                        maxV = [nums[j], j]
                    elif nums[j] <= minV[0]:  # 更新最小值
                        minV = [nums[j], j]
                    if maxV[0] - minV[0] > 2:  # 如果当前最大值和最小值的差大于2
                        k = 1
                        while k <= j and abs(nums[j] - nums[j - k]) <= 2:  # 判断j处的元素能扩展多远
                            k += 1
                        else:
                            s = (j - i + 1) * (j - i) / 2 - (j - i) - (k * (k - 1) / 2 - k + 1)
                            i = j - k + 1  # 调整起始指针i
                            ans += s  # 加入当前计算的子数组数目
                        break
                else:
                    ans += (j - i + 2) * (j - i + 1) / 2 - (j - i + 1)  # 加入所有可能的子数组计数
                    break
        return int(ans + n)  # 返回总数，加上单个元素的子数组数量

Explore

在算法中，maxV和minV的值通过迭代更新，而不是在每次循环中重新计算。每当新的元素被考虑加入到子数组中时，算法检查这个元素是否大于当前的maxV或小于当前的minV，并相应地更新这两个值。这种方法有效利用了前一步的结果，避免了重复的计算，提高了效率。

当maxV和minV的差大于2时，说明当前子数组已经不满足问题中的条件，即子数组中的任意两个数的差不得超过2。这时内部while循环检查`abs(nums[j] - nums[j - k]) <= 2`是为了回溯并找到最大的符合条件的子数组。这个条件确保即使当前元素导致子数组整体不满足条件，子数组的前一部分仍可能有效。

新的i的位置是根据内部while循环的结果确定的，即从当前不满足条件的位置回溯到最后一个可能的有效子数组的起始位置。这种调整是为了尽可能包含更多的元素，同时保证算法效率。理论上，这种方法不会遗漏有效的子数组，因为它是基于当前元素导致的不满足条件来回溯并调整的。

算法使用的数学公式基于组合数学原理来计算子数组数量。公式`(j - i + 2) * (j - i + 1) / 2 - (j - i + 1)`计算的是从i到j的所有可能的子数组数目，减去单独包含j的情况，以避免重复计数。这个计算是正确的，并能有效地计算出所有可能的子数组数量。