Qayta oynash oynashda maksimalni qanday e'lon qilish va saqlash mumkin?

Oyning harakatlanishi bilan maksimalni saqlash uchun ko'pincha ma'lumotlar tuzilmasi ishlatiladi: ikki tomonlama navbat (deque). G'oya shundan iboratki:

• Yangi element qo'shilganda, oxiridan barcha kichik elementlar olib tashlanadi, chunki ular maksimal bo'lishi mumkin emas.
• Oyna harakatlanayotganda, boshlanishidan oyna chegarasidan chiqib ketgan elementlar olib tashlanadi.

Bu hozirgi oynada maksimalni O(1) da olish imkonini beradi va butun massivni O(n) da ishlash imkonini beradi.

Python misoli:

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # indekslarni saqlaydi
    result = []
    for i, num in enumerate(nums):
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if dq[0] == i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

# Foydalanish misoli
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))  # [3,3,5,5,6,7]