O(n) 时间内滑动窗口最大值

Question

输入：

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

输出：

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

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

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当您在 length 列表上滑动 length 的窗口时n，您会维护当前窗口中所有元素的双端队列，这些元素可能在某个时刻成为任何窗口中的最大值。

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

由于双端队列中的每个元素都>其后的所有元素，因此双端队列中的元素是单调递减的，因此第一个元素是当前窗口中的最大元素。

当窗口向右滑动一个位置时，您可以按如下方式维护此双端队列：从末尾删除所有 <= 新元素的元素。然后，将新元素添加到双端队列的末尾。如果从窗口前面掉落的元素是双端队列中的第一个元素，则将其删除。由于每个元素最多添加和删除一次，因此维护此双端队列所需的总时间为 O(n)。

为了更容易判断双端队列前面的元素何时落出窗口，请将元素的索引而不是它们的值存储在双端队列中。

这是一个相当有效的 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