滑动窗口在O（n）时间内的最大值

Question

输入：

listi = [9, 7, 8, 4, 6, 1, 3, 2, 5]

输出：

# m=3
listo = [9, 8, 8, 6, 6, 3, 5]

给定一个由n个数组成的随机列表，我需要找到mconsequentive元素的所有子列表，从子列表中选择最大值并将它们放入新列表中

def convert(listi, m):
    listo = []
    n = len(listi)
    for i in range(n-m+1):
        listo.append(max(listi[i:3+i]))
    return listo

这个实现的时间复杂度是O(m\^{(n-m+1)}，如果listi很长，这是非常糟糕的，有没有办法在O(n)的复杂度中实现这一点

Answer 1

令人惊讶的是，该算法的易于访问的描述并不那么容易理解，因此关键在于：

当您将一个长度为m的窗口滑动到长度为n的列表上时，您将维护当前窗口中所有元素的名称，可能在某个时候成为任何窗口中的最大值

如果当前窗口中的元素大于该窗口中其后出现的所有元素，则该元素可能成为最大值。请注意，这始终包括当前窗口中的最后一个元素

因为deque中的每个元素都是>；在它之后的所有元素，deque中的元素都是单调递减的，因此第一个元素是当前窗口中的最大元素

当窗口向右滑动一个位置时，可以按如下方式保持此形状：从末端移除所有<；=新元素。然后，将新元素添加到deque的末尾。如果从窗口前部掉落的图元是网格中的第一个图元，则将其删除。由于每个元素最多只能添加和删除一次，因此维护此数据所需的总时间为O（n）

为了便于判断deque前面的元素何时掉出窗口，请在deque中存储元素的索引，而不是它们的值

下面是一个相当高效的python实现：

def windowMax(listi, m):
    # the part of this list at positions >= qs is a deque
    # with elements monotonically decreasing.  Each one
    # may be the max in a window at some point
    q = []
    qs = 0

    listo=[]
    for i in range(len(listi)):

        # remove items from the end of the q that are <= the new one
        while len(q) > qs and listi[q[-1]] <= listi[i]:
            del q[-1]

        # add new item
        q.append(i)

        if i >= m-1:
            listo.append(listi[q[qs]])
            # element falls off start of window
            if i-q[qs] >= m-1:
                qs+=1

        # don't waste storage in q. This doesn't change the deque
        if qs > m:
            del q[0:m]
            qs -= m
    return listo

Answer 2

有一个漂亮的解决方案，其运行时间与M无关

在下图中，第一行表示初始序列。在第二行中，我们有从左到右的1、2、…M个连续元素组的最大值（“前缀”最大值）。在第三行，我们有从右到左的1，2，…M个连续元素组的最大值（“后缀”最大值）。第四行是第二行和第三行元素的最大值

a   b   c    d    e    f    g    h    i    j    k    l    m    n    o

a   ab  abc  d    de   def  g    gh   ghi  j    jk   jkl  m    mn   mno
        abc  bc   c    def  ef   f    ghi  hi   i    jkl  kl   l    mno  no   o

        abc  bcd  cde  def  efg  fgh  ghi  hij  ijk  jkl  klm  lmn  mno          

注意，第三行中有复制的元素，我们不需要计算它们

第二行的计算对M个元素的每个切片进行M-1次比较；第二行是M-2，第三行是M。因此忽略末尾的影响，我们对每个元素执行的比较略少于3次

所需的存储是一个额外的M元素数组，用于临时评估第三行的切片

Answer 3

我尝试使用zip计时，结果似乎比您当前的函数快50%——但实际上无法分辨时间复杂度的差异

import timeit

setup = """
from random import randint
listi = [randint(1,100) for _ in range(1000)]

def convert(iterable, m):
    t = [iterable[x:] for x in range(m)]
    result = [max(combo) for combo in zip(*t)]
    return result"""

print (min(timeit.Timer('a=listi; convert(a,3)', setup=setup).repeat(7, 1000)))
#0.250054761


setup2 = """
from random import randint
listi = [randint(1,100) for _ in range(1000)]

def convert2(listi, m):
    listo = []
    n = len(listi)
    for i in range(n-m+1):
        listo.append(max(listi[i:3+i]))
    return listo"""

print (min(timeit.Timer('a=listi; convert2(a,3)', setup=setup2).repeat(7, 1000)))
#0.400374625