数组元素最大的连续子数组的数量

Question

给定一个'n'整数数组，我需要为该数组的每个元素查找以该元素为最大元素的连续子数组的数量。

元素可以重复。

有没有办法做到小于O（n ^ 2）。

O（nlogn）还是O（n）？

Example-
If array is {1,2,3}. Then-
For '1': 1 Such subarray {1}.
For '2': 2 Such subarrays {2},{1,2}
For '3': 3 Such subarrays {3},{2,3},{1,2,3}

Answer 1

您可以将子数组的大小存储在另一个数组 ( arr2) 中，以避免重新计算它们。

arr2必须是最大值的长度arr1

IE -

取数组{1,2,4,6,7,8}

arr2声明如下：

arr2 = []
for i in range(max(arr1)):
    arr2.append(0)

现在，算法是这样的：

假设你击中了 6 号。

由于6-1=5不存在，因此它具有与in 中的0索引相对应的默认值，因为尚未添加任何内容。所以你存储在的位置。然后你就按了号码。您检查是否存在于. 确实如此，值为. 因此将 的值添加到中的位置。5arr20+1=16arr277-1=6arr211+1=27arr2

对于 中的每个值，arr2我们只需将其添加到计数中即可。我们可以同时使用count变量来执行此操作。

这个算法是O(n)