Чӣ гуна эълон кардан ва нигоҳ доштани максимум дар ҳангоми ҳаракати тиреза?

Барои нигоҳ доштани максимума дар тиреза ҳангоми ҳаракат кардани тиреза, аксар вақт структураи додаҳо истифода мешавад: навбатдории дуҷониба (deque). Ҳикоя дар он аст, ки индексҳои элементҳоро дар тартиби коҳишёбандаи арзишҳо нигоҳ доред, то:

• Вақте ки як элемент нав илова мекунед, ҳамаи элементҳои хурдтарро аз охир хориҷ мекунед, зеро онҳо наметавонанд максимум бошанд.
• Вақте ки тирезаро ҳаракат медиҳед, элементҳое, ки аз ҳадди тиреза хориҷ шудаанд, аз оғози навбат хориҷ мешаванд.

Ин имкон медиҳад, ки максимум дар тирезаи ҳозира дар O(1) гирифта шавад ва тамоми массив дар O(n) коркард шавад.

Масалан дар Python:

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # нигоҳ медорад индексҳоро
    натиҷа = []
    барои i, num дар enumerate(nums):
        дар ҳоле ки dq ва nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        агар dq[0] == i - k:
            dq.popleft()
        агар i >= k - 1:
            натиҷа.append(nums[dq[0]])
    return натиҷа

# Мисоли истифода
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))  # [3,3,5,5,6,7]