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

这是O（n）的略图。

对于每个元素，确定左边的连续元素不多（称为a），右边的相邻元素少（称为this 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树，其值不是数字而是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]))