როგორ გამოვაცხადოთ და შევინარჩუნოთ მაქსიმუმი ფანჯრის გადატანისას?

როცა ფანჯრის მაქსიმუმის შენარჩუნება ხდება ფანჯრის გადაადგილებისას, ხშირად გამოიყენება მონაცემთა სტრუქტურა: ორმხრივი რიგი (deque). იდეა მდგომარეობს იმაში, რომ ინახავდეს ელემენტების ინდექსებს მცირდებარე მნიშვნელობების წესით, რათა:

• ახალი ელემენტის დამატებისას, ყველა პატარა ელემენტი ამოღებულ იქნას ბოლო მხრიდან, რადგან ისინი მაქსიმუმი ვერ იქნებიან.
• ფანჯრის გადაადგილებისას, ფანჯრის საზღვრებს მიღმა გასულ ელემენტებს ამოიღებს დასაწყისიდან.

ეს საშუალებას იძლევა მიიღოთ მიმდინარე ფანჯრის მაქსიმუმი O(1) დროში, და მთელი მასივის დამუშავება O(n) დროში.

Python-ის მაგალითი:

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # ინახავს ინდექსებს
    შედეგი = []
    for i, num in 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]])
    վերադարձնել შედეგი

# Օգտագործման օրինակ
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))  # [3,3,5,5,6,7]