Kā deklarēt un uzturēt maksimumu, pārvietojot logu?

Lai saglabātu maksimālo vērtību logā, pārvietojot logu, bieži izmanto datu struktūru: divvirzienu rindu (deque). Ideja ir glabāt elementu indeksus dilstošā vērtību secībā, lai:

• Pievienojot jaunu elementu, no beigām tiek izņemti visi mazāki elementi, jo tie nevar būt maksimālie.
• Pārvietojot logu, no sākuma tiek izņemti elementi, kas iznākuši ārpus loga robežām.

Tas ļauj iegūt pašreizējā loga maksimumu O(1) laikā, un apstrādāt visu masīvu O(n) laikā.

Python piemērs:

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # glabā indeksus
    rezultāts = []
    for i, num in enumerate(nums):
        kamēr dq un nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        ja dq[0] == i - k:
            dq.popleft()
        ja i >= k - 1:
            rezultāts.append(nums[dq[0]])
    return rezultāts

# Piemērs lietošanai
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))  # [3,3,5,5,6,7]