给定一个整数数组 arr，您的任务是计算表示至少两个元素的锯齿序列的连续子数组的数量。
对于 arr = [9, 8, 7, 6, 5]，输出应为 countSawSubarrays(arr) = 4。由于所有元素均按降序排列，因此不可能形成任何长度的锯齿子数组3个或更多。有 4 个可能的子数组包含两个元素，所以答案是 4。
对于 arr = [10, 10, 10]，输出应为 countSawSubarrays(arr) = 0。由于所有元素都相等，因此没有任何子数组可以是锯齿形的，因此答案为 0。
对于 arr = [1, 2, 1, 2, 1]，输出应为 countSawSubarrays(arr) = 10。
所有包含至少两个元素的连续子数组都满足问题的条件。有 10 个可能的连续子数组，其中至少包含两个元素，因此答案是 10。
解决这个问题的最佳方法是什么？我在这里看到了一个可能的解决方案：https://medium.com/swlh/sawtooth-sequence-java-solution-460bd92c064
但是对于 [1,2,1,3,4,-2] 的情况，这段代码失败了，答案应该是 9，但结果却是 12。
我什至尝试过暴力方法，但我无法理解它。任何帮助将不胜感激！
编辑： 感谢 Vishal 的回复，经过一些调整，这里是 python 中的更新解决方案。 时间复杂度：O(n) 空间复杂度：O(1)
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
在做类似的练习题时，我在这个问题上停留了一段时间，然后终于有了一个“啊哈”的时刻，并得到了一个非常简短而优雅的解决方案。
[1, 2, 1, 2, 1][1, 7, 3, 4, 5]3[1, 7][7, 3][3, 4][4, 5][3, 4]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
这可以通过将数组拆分为多个锯齿序列来解决。这是 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;
}
这是我使用动态规划的解决方案。这对我来说比接受的答案（或OP中添加的答案）更具可读性，尽管可能仍有改进的空间。
O(n) 时间和 O(1) 空间。
def solution(arr):
# holds the count of sawtooths at each index of our input array,
# for sawtooth lengths up to that index
saws = [0 for x in range(0, len(arr))]
# the resulting total sawtooth counts
totalSawCounts = 0
previousCount = 0
for currIdx in range(1, len(arr)):
currCount = 0
before = currIdx -1
if (arr[currIdx] > arr[before]):
goingUp = True
elif (arr[currIdx] < arr[before]):
goingUp = False
else:
break
# if we made it here, we have at least one sawtooth
currCount = 1
# see if there was a previous solution (the DP part)
# and if it continues our current sawtooth
if before >= 1:
if goingUp:
if arr[before-1] > arr[before]:
currCount = previousCount + currCount
else:
if arr[before-1] < arr[before]:
currCount = previousCount + currCount
previousCount = currCount
totalSawCounts = totalSawCounts + currCount
return totalSawCounts
测试用例：
arr = [9,8,7,6,5]
print(solution(arr)) # 4
arr2 = [1,2,1,3,4,-2]
print(solution(arr2)) # 9
arr3 = [1,2,1,2,1]
print(solution(arr3)) # 10
arr4 = [10,10,10]
print(solution(arr4)) # 0
# from medium article comments
arr5 = [-442024811,447425003,365210904,823944047,943356091,-781994958,872885721,-296856571,230380705,944396167,-636263320,-942060800,-116260950,-126531946,-838921202]
print(solution(arr5)) # 31
我认为这是一个简单的DP问题。这个想法是为了知道可以从之前的交替状态（增加/减少）扩展的以 i 结尾的子数组的数量。如果当前元素低于前一个元素，它可以对在前一个状态 (i-1) 结束的已经增加的子数组做出贡献，反之亦然。
#include <bits/stdc++.h>
using namespace std;
void solve(vector<int> arr) {
int n = arr.size(), ans = 0;
// vector<vector<int>> dp(n, vector<int>(2, 0));
int inc = 0, dec = 0;
for(int i = 1; i < n; i++) {
if (arr[i] > arr[i-1]) {
// dp[i][0] = dp[i-1][1] + 1;
inc = dec + 1;
dec = 0;
} else if (arr[i] < arr[i-1]) {
// dp[i][1] = dp[i-1][0] + 1;
dec = inc + 1;
inc = 0;
} else {
inc = 0, dec = 0;
}
// ans += dp[i][0] + dp[i][1];
ans += (inc + dec);
}
cout << ans << endl;
}
int main() {
auto inp = {-442024811,447425003,365210904,823944047,943356091,-781994958,872885721,-296856571,230380705,944396167,-636263320,-942060800,-116260950,-126531946,-838921202};
solve(inp);
return 0;
}
下面是一个非常简单直接的解决方案，只有一个 for 循环
import math
def comb(x):
st = 0
total_comb = 0
if len(x) < 2: #edge case
return 0
if len(x) == 2: #edge case
return 2
seq_s = 0
for i in range(1, len(x)-1):
if (x[i]<x[i-1] and x[i]<x[i+1]) or (x[i]>x[i-1] and x[i]>x[i+1]):
continue
else:
print(x[seq_s:i+1])
if i+1-seq_s == 2 and x[i] == x[i-1]: #means we got two same nums like 10, 10
pass
else: total_comb+=math.comb(i+1-seq_s,2)
seq_s=i
i+=1
print(x[seq_s:])
if i+1-seq_s == 2 and x[i] == x[i-1]: #means we got two same nums like 10, 10
pass
else: total_comb+=math.comb(len(x)-seq_s,2)
return total_comb
x= [1,2,1,3,4,-2]
print(comb(x))
采用梯度法。
通过所有测试用例
from math import comb
def solution(arr):
n=len(arr)
if arr[1]!=arr[0]:
l=2
else:
l=0
pre=arr[1]-arr[0]
ans=0
for i in range(2,n):
cur=arr[i]-arr[i-1]
if cur*pre<0:
l+=1
else:
if l==2:
ans+=1
elif l==0:
ans+=0
else:
ans+=comb(l,2)
if cur!=0:
l=2
else:
l=0
pre=cur
if l==2:
ans+=1
elif l==0:
ans+=0
else:
ans+=comb(l,2)
return ans
我认为这里的技巧是要认识到：假设您有一个长度为
xx示例：
[1,2,1]将 2 添加到这个有效的
[1,2,1][1,2,1,2][1,2,1,2][2,1,2][1,2]相应地，在
-1[1,2,1,2][1,2,1,2,-1][2,1,2,-1][1,2,-1][2,-1]因此，我们可以使用带有左右指针
lrl.
def solution(arr: list) -> int:
'''
for every char, check if still current sawtooth
if still currently sawtooth, numberOfWays += length
else reset temp counter
'''
l, r = 0, 1
ways = 0
while r < len(arr):
# check if current char + past 2 chars are sawtooth
if r-l > 1 and (arr[r-2] < arr[r-1] > arr[r] or
arr[r-2] > arr[r-1] < arr[r]):
ways += r-l
# check if current char + past 1 chars are sawtooth
elif arr[r-1] != arr[r]:
ways += 1
l = r-1
else:
# reset left pointer
l = r
r += 1
return ways
我做了一些非常简单的事情，但它为您提供的所有测试用例提供了正确的答案：
function sawtooth(arr) {
if (arr.length < 2) return 0;
let previousLongest = 1;
let result = 0;
for (let i = 1; i < arr.length; i++) {
if (i >= arr.length) break;
if (arr[i - 1] === arr[i]) continue;
if (arr[i - 1] > arr[i] && arr[i] < arr[i + 1] || arr[i - 1] < arr[i] && arr[i] > arr[i + 1]) {
previousLongest += 1;
} else {
previousLongest = 1;
}
result += previousLongest;
}
return result;
}
我遇到了同样的问题，并采取了与@appu类似的方法，但我跟踪负面/正面变化的方式略有不同。
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return 0
last_sign = None
count = 0 # total number of sawteeth
streak = 0
for i in range(1, n):
if nums[i] == nums[i - 1]:
last_sign = None
streak = 0
continue
diff = nums[i] - nums[i - 1]
# handle positive/negative changes
if (diff > 0 and last_sign != 1) or (diff < 0 and last_sign != -1):
streak += 1
last_sign = 1 if diff > 0 else -1
else:
# handle broken streak
streak = 1
count += streak
return count