<p>令人惊讶的是,该算法的易于访问的描述并不那么容易理解,因此关键在于:</p>
<p>当您将一个长度为<code>m</code>的窗口滑动到长度为<code>n</code>的列表上时,您将维护当前窗口中所有元素的名称,<em>可能在某个时候成为任何窗口中的最大值</p>
<p>如果当前窗口<em>中的元素大于该窗口中其后出现的所有元素,则该元素可能</em>成为最大值。请注意,这始终包括当前窗口中的最后一个元素</p>
<p>因为deque中的每个元素都是>;在它之后的所有元素,deque中的元素都是单调递减的,因此第一个元素是当前窗口中的最大元素</p>
<p>当窗口向右滑动一个位置时,可以按如下方式保持此形状:从末端移除所有<;=新元素。然后,将新元素添加到deque的末尾。如果从窗口前部掉落的图元是网格中的第一个图元,则将其删除。由于每个元素最多只能添加和删除一次,因此维护此数据所需的总时间为O(n)</p>
<p>为了便于判断deque前面的元素何时掉出窗口,请在deque中存储元素的<em>索引</em>,而不是它们的值</p>
<p>下面是一个相当高效的python实现:</p>
<pre><code>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
</code></pre>