Терезе жылжытканда максимумду кантип жарыялап жана сактап калуу керек?

Терезе жылжып жатканда максимумду сактоо үчүн көбүнчө маалымат түзүмү колдонулат: эки тараптуу кезек (deque). Ой жүгүртүү идеясы — элементтердин көрсөткүчтөрүн алардын маанилери төмөндөп бара жаткан тартипте сактоо, ошондуктан:

• Жаңы элемент кошулганда, акыркы жагынан бардык кичинекей элементтер алынып салынат, анткени алар максимум болушу мүмкүн эмес.
• Терезе жылжып жатканда, терезенин чегинен чыгып кеткен элементтер баштан алынып салынат.

Бул учурда, учурдагы терезедеги максимум O(1) убакытта алынып, бүт массив O(n) убакытта иштетилет.

Python мисалы:

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # көрсөткүчтөрдү сактайт
    натыйжа = []
    үчүн i, num in enumerate(nums):
        while 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]