滑动窗口的最大值为O（n）时间 [英] Sliding window maximum in O(n) time
问题描述
输入：
listi = [9, 7, 8, 4, 6, 1, 3, 2, 5]
输出：
# m=3
listo = [9, 8, 8, 6, 6, 3, 5]
给出一个由 n 个数字组成的随机列表，我需要找到所有 m 相应的元素，请从子列表中选择最大值，然后将它们放在新列表中。
Given a random list composed of n numbers, I need to find all of the sublists of m consequtive elements, choose the largest value from the sublist and put them in a new list.
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）来实现这一点？
The time complexity for this implementation is O(m\^{(n-m+1)}, which is pretty bad if listi is long, is there a way to implement this in the complexity of O(n)?
推荐答案
令人惊讶的是，该算法的易于访问的描述并不那么容易理解，因此三ck是这样的：
Surprisingly, the easily accessible descriptions of this algorithm are not that easy to understand, so the trick is this:
在长度为
As you slide a window of length m over your list of length n, you maintain a deque of all the elements in the current window that might, at some point, become the maximum in any window.
当前窗口中的一个元素可能如果大于该窗口中所有在其后出现的元素，则变为最大值。请注意，这始终包括当前窗口中的最后一个元素。
An element in the current window might become the maximum if it is greater than all the elements that occur after it in the window. Note that this always includes the last element in the current window.
由于双端队列中的每个元素都大于其后的所有元素，因此双端队列中的元素单调递减，因此，第一个是当前窗口中的最大元素。
Since every element in the deque is > all the elements after it, elements in the deque are monotonically decreasing, and the first one is therefore the maximum element in the current window.
当窗口向右滑动一个位置时，可以按以下方式保持此双端队列：删除所有末尾的< =新元素。然后，将新元素添加到双端队列的末尾。如果从窗口前面掉落的元素是双端队列中的第一个元素，则将其删除。由于每个元素最多只能添加和删除一次，因此维护此双端队列所需的总时间为O（n）。
As the window slides one position to the right, you can maintain this deque as follows: remove all the elements from the end that are <= the new element. Then, add the new element to the end of the deque. If the element that drops off the front of the window is the first element in the deque, then remove it. Since each element is added and removed at most one time, the total time required to maintain this deque is in O(n).
为了便于区分何时双端队列前端的元素从窗口中掉出，将元素的索引而不是其值存储在双端队列中。
To make it easy to tell when an element at the front of the deque is falls out of the window, store the elements' indexes in the deque instead of their values.
一个合理有效的python实现：
Here's a reasonably efficient python implementation:
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）时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
