计算连续锯齿状子数组

Question

给定一个整数数组 arr，您的任务是计算表示至少两个元素的锯齿序列的连续子数组的数量。

\n

对于 arr = [9, 8, 7, 6, 5]，输出应为 countSawSubarrays(arr) = 4。由于所有元素均按降序排列，因此 \xe2\x80\x99 不可能形成任何锯齿波长度为 3 或以上的子数组。有 4 个可能的子数组包含两个元素，因此答案是 4。

\n

对于 arr = [10, 10, 10]，输出应为 countSawSubarrays(arr) = 0。由于所有元素都相等，因此没有任何子数组可以是锯齿形的，因此答案为 0。

\n

对于 arr = [1, 2, 1, 2, 1]，输出应为 countSawSubarrays(arr) = 10。

\n

所有包含至少两个元素的连续子数组都满足问题的条件。有 10 个可能的连续子数组包含至少两个元素，因此答案是 10。

\n

解决这个问题的最佳方法是什么？我在这里看到了一个可能的解决方案：https ://medium.com/swlh/sawtooth-sequence-java-solution-460bd92c064

\n

但这段代码对于 [1,2,1,3,4,-2] 的情况失败了，其中答案应该是 9，但结果却是 12。

\n

我什至尝试过暴力方法，但我无法理解它。任何帮助，将不胜感激！

\n

编辑： \n感谢 Vishal 的回复，经过一些调整，这里是 python 中的更新解决方案。\n时间复杂度：O(n)\n空间复杂度：O(1)

\n

def samesign(a,b):\n    if a/abs(a) == b/abs(b):\n        return True\n    else:\n        return False\n\ndef countSawSubarrays(arr):\n    n = len(arr)\n    \n    if n<2:\n        return 0\n\n    s = 0\n    e = 1\n    count = 0\n    \n    while(e<n):\n        sign = arr[e] - arr[s]\n        while(e<n and arr[e] != arr[e-1] and samesign(arr[e] - arr[e-1], sign)):\n            sign = -1*sign\n            e+=1\n        size = e-s\n        if (size==1):\n            e+=1\n        count += (size*(size-1))//2\n        s = e-1\n        e = s+1\n    return count\n\narr1 = [9,8,7,6,5]\nprint(countSawSubarrays(arr1))\narr2 = [1,2,1,3,4,-2]\nprint(countSawSubarrays(arr2))\narr3 = [1,2,1,2,1]\nprint(countSawSubarrays(arr3))\narr4 = [10,10,10]\nprint(countSawSubarrays(arr4))\n

\n

结果:\n4\n9\n10\n0

\n

Answer 1

在做类似的练习题时，我在这个问题上停留了一段时间，然后终于有了一个“啊哈”的时刻，并得到了一个非常简短而优雅的解决方案。

• 当我们迭代时，每次我们在子数组长度 2 的增加和减少之间翻转时，连续数组的数量就会增加当前连续翻转的次数。例如，[1, 2, 1, 2, 1]连续翻转 4 次，因此 1 + 2 + 3 + 4 = 10
• 当我们突破锯齿状条纹时，即当我们连续增加两次或连续减少两次时，最长的连续子数组现在只有 2，因此如果两个值不相等，我们将计数器重置为 1 (因为这是一个有效的锯齿）或 0（如果值相同）。
• 条纹和断裂条纹的示例：[1, 7, 3, 4, 5]. 3我们在迭代 ( [1, 7], [7, 3], ) 时保持一条连续[3, 4]，然后[4, 5]打破这个连续，因为[3, 4]它也在增加，所以我们最终的计数为 (3 + 2 + 1) + 1 = 7 个可能的锯齿。

def solution(arr):
    if len(arr) < 2:
        return 0

    count = 0
    streak = 0
    prev_increasing = None

    for i in range(1, len(arr)):
        if arr[i] == arr[i-1]:
            prev_increasing = None
            streak = 0
        else:
            curr_increasing = arr[i] > arr[i-1]
            if curr_increasing != prev_increasing:
                # keep track of streak of flips between increasing and decreasing
                streak += 1
                prev_increasing = curr_increasing
            else:
                # when we break out of a streak, we reset the streak counter to 1
                streak = 1

            # number of sawtooth contiguous subarrays goes up by the current streak
            count += streak

    return count

Answer 2

这可以通过将数组分割成多个锯齿序列来解决......这是 O(n) 操作。例如 [1,2,1,3,4,-2] 可以分为两个序列 [1,2,1,3] 和 [3,4,-2]，现在我们只需要做 C(size ,2) 两个部分的操作。

这是解释这个想法的伪代码（没有处理所有极端情况）

 public int countSeq(int[] arr) {
int len = arr.length;
if (len < 2) {
  return 0;
}

int s = 0;
int e = 1;
int sign = arr[e] - arr[s];
int count = 0;

while (e < len) {
  while (e < len && arr[e] - arr[e-1] != 0 && isSameSign(arr[e] - arr[e-1], sign)) {
    sign = -1 * sign;
    e++;
  }
  // the biggest continue subsequence starting from s ends at e-1;
  int size = e - s;
  count = count + (size * (size - 1)/2); // basically doing C(size,2)
  s = e - 1;
  e = s + 1;
}

return count;

}