连续锯齿子数组计数问题解法及O(n)复杂度最优实现解析

问题描述 #

给定整数数组arr，需要统计其中满足锯齿序列定义、且长度至少为2的连续子数组的总个数。

测试用例示例 #

• 示例1：arr = [9, 8, 7, 6, 5]，输出为4。数组完全降序，无法构造长度≥3的锯齿子数组，仅4个长度为2的子数组符合要求。
• 示例2：arr = [10, 10, 10]，输出为0。所有元素相等，不存在符合要求的锯齿子数组。
• 示例3：arr = [1, 2, 1, 2, 1]，输出为10。该数组所有长度≥2的连续子数组都符合锯齿序列要求，总计10个。

解法说明 #

此前找到的参考解法存在逻辑缺陷，在测试用例[1,2,1,3,4,-2]上运行结果为12，与正确结果9不符。经过调整后得到如下时间复杂度O(n)、空间复杂度*O(1)*的正确Python实现：

def samesign(a,b):
    if a/abs(a) == b/abs(b):
        return True
    else:
        return False

def countSawSubarrays(arr):
    n = len(arr)
    
    if n < 2:
        return 0

    s = 0
    e = 1
    count = 0
    
    while(e < n):
        sign = arr[e] - arr[s]
        while(e < n and arr[e] != arr[e-1] and samesign(arr[e] - arr[e-1], sign)):
            sign = -1*sign
            e += 1
        size = e - s
        if size == 1:
            e += 1
        count += (size * (size - 1)) // 2
        s = e - 1
        e = s + 1
    return count

# 测试用例
arr1 = [9,8,7,6,5]
print(countSawSubarrays(arr1))
arr2 = [1,2,1,3,4,-2]
print(countSawSubarrays(arr2))
arr3 = [1,2,1,2,1]
print(countSawSubarrays(arr3))
arr4 = [10,10,10]
print(countSawSubarrays(arr4))

运行结果 #

4
9
10
0

内容的提问来源于stack exchange，提问作者Divyam Khanna