令人惊讶的是,此算法的易于理解的描述并不那么容易理解,所以诀窍是:
在将长度窗口滑动到长度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