CKTIS / Python
Добавяне в десния край на `deque`
`collections.deque.append` добавя един елемент в десния край на двустранна опашка. В този пример с плъзгащ се прозорец монотонната опашка съхранява индексите вместо самите стойности.
Версия: Python 3.12
Синтаксис
d.append(x) # d is a collections.deque; x is passed positionally; returns NoneВ Python 3.12 collections.deque.append е метод на типа deque от модула collections. При извикване на d.append(x) подаваш x като позиционен аргумент. Методът добавя x като един елемент в десния край, дори ако x е итерируем обект. Той променя самия d и връща None, затова не пиши d = d.append(x). Използвай appendleft(x) за добавяне отляво или extend(iterable) за добавяне на елементите на итерируем обект отдясно.
И list.append, и deque.append добавят в края. За опашките важната разлика е, че добавянето и премахването в двата края на deque отнемат приблизително O(1) време, докато list.pop(0) измества останалите елементи и отнема O(n) време.
Ако maxlen е пропуснат или е None, deque няма фиксирано ограничение на дължината. Когато deque с положителен maxlen се запълни, append автоматично премахва най-левия елемент, вместо да предизвика изключение заради запълването. При maxlen=0 не се запазват елементи. Примерът използва deque без ограничение: индексът излиза от прозореца според позицията си във входните данни, а не според броя на кандидатите.
За да намериш максимумите в плъзгащ се прозорец, премахни отляво с popleft() индексите, които вече са извън прозореца. После с pop() премахни отдясно индексите, чиито стойности са по-малки или равни на новата стойност. При равни стойности по-новият индекс остава по-дълго в прозореца. Накрая извикай candidates.append(i) върху deque: запази индекса i, а за сравненията използвай values[i]. Стойностите на оставащите индекси намаляват отляво надясно, затова при пълен прозорец values[candidates[0]] е максимумът.
Примери
from collections import deque
values = [4, 2, 2, 5, 3, 1, 2]
width = 3
candidates = deque()
maxima = []
for i, value in enumerate(values):
while candidates and candidates[0] <= i - width:
candidates.popleft()
while candidates and values[candidates[-1]] <= value:
candidates.pop()
candidates.append(i)
if i >= width - 1:
maxima.append(values[candidates[0]])
print(maxima)
Резултат
[4, 5, 5, 5, 3]
Когато се появи втората стойност `2`, нейният индекс `2` заменя индекс `1`. В последния прозорец индекс `3` със стойност `5` излиза от прозореца и се премахва отляво. Тогава максимумът е `3`.
Свързани уроци
- Python · Урок 41 · Напреднало · Версия: 5