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

  • Z时代
  • 2024-01-10
  • 分类：问答

输入：

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)呢？

回答：

令人惊讶的是，此算法的易于理解的描述并不那么容易理解，所以诀窍是：

在将长度窗口滑动到长度m列表上时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

以上是 滑动窗口的最大值为O（n）时间 的全部内容， 来源链接： utcz.com/qa/423104.html

回到顶部