最近我遇到了一个问题。算法的一部分需要计算长度为K的滑动窗口的最大元素之和。其中,K的范围为1≤K≤N(N是数组的长度)。
例如,如果我有一个数组A:
长度为1的滑动窗口:
长度为2的滑动窗口:
长度为3的滑动窗口:
长度为4的滑动窗口:
我尝试过使用O(N^2)的方法。对于长度为K的每个滑动窗口,我可以在O(N)的时间内计算出最大值。由于K的范围是N,因此总体复杂度为O(N^2)。
我正在寻找O(N)或O(NlogN)或类似于这种算法,因为N可能高达10^5。
注意:数组中的元素可能非常大,最终答案要对10^9+7取模。
编辑:我实际上想要在总体线性时间或O(NlogN)内找到每个K值(即从0到N),而不是在O(KN)或O(KNlogN)的时间内找到它们,其中K={1,2,3,.... N}。
例如,如果我有一个数组A:
5,3,12,4
长度为1的滑动窗口:
5 + 3 + 12 + 4 = 24
长度为2的滑动窗口:
5 + 12 + 12 = 29
长度为3的滑动窗口:
12 + 12 = 24
长度为4的滑动窗口:
12
最终答案是24、29、24、12
。我尝试过使用O(N^2)的方法。对于长度为K的每个滑动窗口,我可以在O(N)的时间内计算出最大值。由于K的范围是N,因此总体复杂度为O(N^2)。
我正在寻找O(N)或O(NlogN)或类似于这种算法,因为N可能高达10^5。
注意:数组中的元素可能非常大,最终答案要对10^9+7取模。
编辑:我实际上想要在总体线性时间或O(NlogN)内找到每个K值(即从0到N),而不是在O(KN)或O(KNlogN)的时间内找到它们,其中K={1,2,3,.... N}。
A[i]=x
。我们查看窗口1..K
的所有size
值。当size=1
时,x
是最大值。当size
增长时,x
可能不再是最大值。一旦它不是最大值(比如在size=m
时),它将不再是最大值。我认为这是解决方案的关键部分。 - shapiro yaacov