Ինչպես հայտարարել և պահել առավելագույնը պատուհանի տեղափոխման ժամանակ?

Որպեսզի պահել առավելագույնը պատուհանում՝ պատուհանը շարժելիս, հաճախ օգտագործվում է տվյալների կառուցվածք՝ երկկողմանի հերթ (deque): Իդեան այն է, որ պահել տարրերի ցուցանիշները նվազող արժեքների կարգով, որպեսզի՝

• Նոր տարր ավելացնելիս, վերջից հեռացվեն բոլոր փոքր տարրերը, քանի որ նրանք չեն կարող լինել առավելագույնը:
• Պատուհանը շարժելիս, սկզբից հեռացվեն այն տարրերը, որոնք դուրս են եկել պատուհանի սահմաններից:

Այս կերպ հնարավոր է ստանալ ընթացիկ պատուհանի առավելագույնը O(1) ժամանակում, և ամբողջ զանգվածը մշակել O(n) ժամանակում:

Python օրինակով:

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # պահում է ցուցանիշները
    արդյունք = []
    համար 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]