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

Question

最近我陷入了困境.算法部分需要计算长度为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

Final answer is 24,29,24,12.

我试过这个O(N ^ 2).对于长度为K的每个滑动窗口,我可以用O(N)计算最大值.由于K高达N.因此,总体复杂度变为O(N ^ 2).
我正在寻找O(N)或O(NlogN)或与此算法类似的东西,因为N可能高达10 ^ 5.
注意:数组中的元素可以大到10 ^ 9,因此输出最终答案为模10 ^ 9 + 7

编辑:我实际上想要找到K的每个值(即从0到N)的答案线性时间或O(NlogN)不在O(KN)或O(KNlogN)中,其中K = {1,2,3,...... N}

Answer 1

这是 O(n) 的简略草图。

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

如果窗口包含该元素并且仅包含a其左侧和b右侧的元素，则该特定元素在其窗口中最大。有用的是，长度为 k 的此类窗口的数量（以及这些窗口的总贡献）在 k 中是分段线性的，最多有 5 个。例如，如果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 树，其值不是数字，而是 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]))