将元素最大的子数组计数为k

Question

给定一个数组和一个数字k，您需要计算其中k是最大值的子数组的数量。

例如，在数组[4，1，2，1，5]和k=3中。所以这个数组的计数是6。

我想出了以下解决方案：

count = 0
n = len(a)
for i in range(n):
for j in range(i,n):
b = a[i:j]
if k in b and max(b) == k:
count += 1
return count

其时间复杂度为O(n^2(。如何优化它(最好使用双指针方法(以获得O(n(解决方案？

Answer 1

列表中唯一k的一个解决方案：

k = 3
a = [4,1,2,3,1,5]
length = len(a)
ucount, lcount = 0, 0
# Find the index of k:
index = a.index(k)
# From this position, go in one direction until a larger number is found
# increment ucount for each step
upper = index
while upper < length and a[upper] <= k:
ucount += 1
upper += 1
# After that, go from index backwards until a larger number is found
# increment lcount for each step
lower = index
while lower >= 0 and a[lower] <= k:
lcount += 1
lower -= 1
# Multiply the upper and lower count
print(ucount*lcount)

最坏的情况是，这是O(n(，用于查找索引，并且在一起循环时，这两种情况都是O(n(。它仍然是O(n(。

另一种解决方案是在遍历列表一次的同时收集lower、index和upper。

对于多次出现的k，情况会变得更加复杂，尤其是当它们重叠时(当它们由数字<k连接时(。