长度为K的滑动窗口内最大元素之和

Question

长度为K的滑动窗口内最大元素之和

6

最近我遇到了一个问题。算法的一部分需要计算长度为K的滑动窗口的最大元素之和。其中，K的范围为1≤K≤N（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}。

- Mike

3

为什么我的问题被踩了，能否告诉我原因，这样我就可以修改问题了。 - Mike

不确定具体细节，但这似乎与某些数学技巧有关。让我们看看项目 A[i]=x。我们查看窗口 1..K 的所有 size 值。当 size=1 时，x 是最大值。当 size 增长时，x 可能不再是最大值。一旦它不是最大值（比如在 size=m 时），它将不再是最大值。我认为这是解决方案的关键部分。 - shapiro yaacov

直觉上，这似乎非常困难：令人惊讶的是，对于特定的K，它可以在O（N）内完成，并且需要将K硬编码到数据结构中。要为所有K执行O（N）似乎非常具有挑战性。另一方面，如果我们可以利用相邻K的某些共同点，那么可能可以实现O（NlogN）？ - strubbly

@shapiro yaacov 如果给出的数组是按照递增或递减顺序排列的呢？那么最坏情况的时间复杂度将会是O(N^2)。如果你有更好的时间复杂度，请在本帖回答。 - Mike

@strubbly - 我认为你所说的“如果我们可以利用相邻K的一些共性...”接近我想表达的意思。当查看单个项目及其周围环境时，我们可以获得有关数组的一些知识... - shapiro yaacov

显示剩余3条评论

3个回答

2

让我们确定每个元素的区间，其中该元素是支配（最大）的。我们可以使用正向和反向运行并使用堆栈在线性时间内完成此操作。数组L和R将包含支配区间的索引。

获取右侧和左侧索引的方法：

Stack.Push(0) //(1st element index)
for i = 1 to Len - 1 do
     while Stack.Peek < X[i] do
         j = Stack.Pop
         R[j] = i   //j-th position is dominated by i-th one from the right
     Stack.Push(i)
while not Stack.Empty
   R[Stack.Pop] = Len  //the rest of elements are not dominated from the right

//now right to left
Stack.Push(Len - 1) //(last element index)
for i = Len - 2 to 0 do
     while Stack.Peek < X[i] do
         j = Stack.Pop
         L[j] = i   //j-th position is dominated by i-th one from the left
     Stack.Push(i)
while not Stack.Empty
   L[Stack.Pop] = -1  //the rest of elements are not dominated from the left

(5,7,3,9,4)数组的结果。
例如，7在0..2间隔中占优势，9在0..4中占优势。

i  0   1   2   3   4 
X  5   7   3   9   4
R  1   3   3   5   5
L -1  -1   1  -1   4

现在我们可以计算每个元素在每个可能的总和中的影响。
元素5支配(0,0)区间，它只在k=1的总和项中被求和。
元素7支配(0,2)区间，在k=1的总和项中被求和一次，在k=2中被求和两次，在k=3中被求和一次。
元素3支配(2,2)区间，它只在k=1的总和项中被求和。
元素9支配(0,4)区间，在k=1的总和项中被求和一次，在k=2中被求和两次，在k=3中被求和两次，在k=4中被求和两次，在k=5中被求和一次。
元素4支配(4,4)区间，它只在k=1的总和项中被求和。
通常情况下，长支配区间的元素位于长数组的中心位置，可以在长度为k的总和中产生最多k*Value的影响（这取决于相对于数组末端和其他支配元素的位置）。

k    1    2    3     4    5
 --------------------------
     5        
     7    2*7  7
     3    
     9    2*9  2*9   2*9  9
     4
 --------------------------
S(k) 28   32   25    18   9

请注意，系数之和为N*(N-1)/2（等于可能窗口的数量），大多数表格条目为空，因此复杂度似乎比O(N^2)更好。
（我仍然对确切的复杂度有疑问）

- MBo

不错的想法，但这仍然是O(N^2)。 - gen-y-s

它仍然是O(N^2)。证明：我们保留一个数组，其中包含每个K值的最大子总计。对于原始数组中的每个元素，我们必须更新子总计数组中的X个K值，其中X是支配区间的大小（例如，具有大小为3的支配区间的元素将添加到K=1、K=2和K=3的子总计中）。因此，总体复杂度是所有元素的支配区间大小之和。在最坏的情况下，这是O(N^2) - 例如，如果原始数组按递增顺序排列，则支配区间大小为1-N，它们的总和为O(N^2)。 - gen-y-s

嘿！看看我上面的证明，为什么你的算法是O(N^2)……根本不比平凡解决方案更好。实际上，我认为O(N^2)是最低限度，就像我在我的答案中所说的那样。“（我仍然怀疑确切的复杂度）”- 不再怀疑了…… - gen-y-s

@gen-y-s 你说的递增顺序最坏情况是正确的。很遗憾:( - MBo

你是正确的... 谢谢!!! 顺便说一句，不仅我是正确的，而且当你无法解决算法复杂度问题时，我也解决了。QED - gen-y-s

0

给定窗口大小的滑动窗口中最大值的总和可以使用双端队列在线性时间内计算，该队列保留当前窗口中的元素。我们维护双端队列，使得队列中的第一个元素（索引0，最左边）始终是当前窗口的最大值。

这是通过迭代数组完成的，在每次迭代中，首先如果双端队列中的第一个元素不再在当前窗口中（我们通过检查其原始位置来判断，该位置也与其值一起保存在双端队列中），则将其删除。然后，我们删除双端队列末尾小于当前元素的任何元素，最后将当前元素添加到双端队列的末尾。

计算大小为K的所有滑动窗口的最大值的复杂度为O(N)。如果您想对从1..N的所有K值进行计算，则时间复杂度将为O(N^2)。 O(N)是计算大小为K的所有窗口的最大值之和的最佳时间（这很容易看出）。要计算其他K值的总和，简单的方法是为每个不同的K值重复计算，这将导致总时间为O(N^2)。有更好的方法吗？没有，因为即使我们保存了一个K值的计算结果，我们也无法在少于O(N)的时间内使用它来计算另一个K值的结果。因此，最佳时间为O(N^2)。

以下是Python实现：

from collections import deque

def slide_win(l, k):
  dq=deque()
  for i in range(len(l)):
    if len(dq)>0 and dq[0][1]<=i-k:
      dq.popleft()
    while len(dq)>0 and l[i]>=dq[-1][0]:
      dq.pop()
    dq.append((l[i],i))
    if i>=k-1:
      yield dq[0][0]

def main():
  l=[5,3,12,4]
  print("l="+str(l))
  for k in range(1, len(l)+1):
    s=0
    for x in slide_win(l,k):
      s+=x
    print("k="+str(k)+" Sum="+str(s))

- gen-y-s

请仔细阅读问题。我已经说明了我可以在O(N)的复杂度下找到任何K的总和。但是我想要在O(N)或O(NlogN)的复杂度下找到所有K的总和。 - Mike

阅读代码 - 主函数调用slide_win函数以获取所有窗口的最大值，然后计算它们的总和。 - gen-y-s

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

以下是关于O(n)的简略概述。

对于每个元素，确定左侧连续不大于它的元素数量（称之为a），以及右侧连续小于它的元素数量（称之为b）。这可以在O(n)的时间内完成——详见MBo的答案。

如果一个特定的元素在其窗口中是最大的，则该窗口只包含该元素、a到其左侧的元素和b到其右侧的元素。有用的是，长度为k的这种窗口的数量（以及这些窗口的总贡献）在k上是分段线性的，最多有五个部分。例如，如果a = 5且b = 3，则有：

1 window  of size 1
2 windows of size 2
3 windows of size 3
4 windows of size 4
4 windows of size 5
4 windows of size 6
3 windows of size 7
2 windows of size 8
1 window  of size 9.

我们需要使用的数据结构来高效地对贡献进行编码是一棵树状数组（Fenwick tree），其中的值不是数字，而是k的线性函数。对于分段线性贡献函数的每个线性部分，我们将其添加到其区间开头的单元格中，并从其结束位置的单元格中减去它（开放开始，闭合结束）。最后，我们检索所有前缀和，并在它们的索引k处对其进行评估，以获取最终数组。

（好了，现在必须走了，但实际上我们并不需要在第二步中使用Fenwick树，这将使其复杂度为O(n)，并且可能还有一种方法可以在线性时间内完成第一步。）

Python 3，轻微测试：

def left_extents(lst):
  result = []
  stack = [-1]
  for i in range(len(lst)):
    while stack[-1] >= 0 and lst[i] >= lst[stack[-1]]:
      del stack[-1]
    result.append(stack[-1] + 1)
    stack.append(i)
  return result


def right_extents(lst):
  result = []
  stack = [len(lst)]
  for i in range(len(lst) - 1, -1, -1):
    while stack[-1] < len(lst) and lst[i] > lst[stack[-1]]:
      del stack[-1]
    result.append(stack[-1])
    stack.append(i)
  result.reverse()
  return result


def sliding_window_totals(lst):
  delta_constant = [0] * (len(lst) + 2)
  delta_linear = [0] * (len(lst) + 2)
  for l, i, r in zip(left_extents(lst), range(len(lst)), right_extents(lst)):
    a = i - l
    b = r - (i + 1)
    if a > b:
      a, b = b, a
    delta_linear[1] += lst[i]
    delta_linear[a + 1] -= lst[i]
    delta_constant[a + 1] += lst[i] * (a + 1)
    delta_constant[b + 2] += lst[i] * (b + 1)
    delta_linear[b + 2] -= lst[i]
    delta_linear[a + b + 2] += lst[i]
    delta_constant[a + b + 2] -= lst[i] * (a + 1)
    delta_constant[a + b + 2] -= lst[i] * (b + 1)
  result = []
  constant = 0
  linear = 0
  for j in range(1, len(lst) + 1):
    constant += delta_constant[j]
    linear += delta_linear[j]
    result.append(constant + linear * j)
  return result

print(sliding_window_totals([5, 3, 12, 4]))