Πώς να δηλώσετε και να διατηρήσετε το μέγιστο κατά την μετακίνηση του παραθύρου;

Για να διατηρήσετε το μέγιστο σε ένα παράθυρο κατά την ολίσθηση του παραθύρου, συχνά χρησιμοποιείται μια δομή δεδομένων: μια διπλή ουρά (deque). Η ιδέα είναι να αποθηκεύετε τους δείκτες των στοιχείων με φθίνουσα σειρά τιμών, έτσι ώστε:

• Κατά την προσθήκη ενός νέου στοιχείου, αφαιρούνται από το τέλος της ουράς όλα τα μικρότερα στοιχεία, καθώς δεν μπορούν να είναι το μέγιστο.
• Κατά την ολίσθηση του παραθύρου, αφαιρούνται από την αρχή της ουράς τα στοιχεία που έχουν εξέλθει από τα όρια του παραθύρου.

Αυτό επιτρέπει την εύρεση του μέγιστου στο τρέχον παράθυρο σε O(1), και την επεξεργασία ολόκληρου του πίνακα σε O(n).

Παράδειγμα σε Python:

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # αποθηκεύει δείκτες
    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

# Παράδειγμα χρήσης
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))  # [3,3,5,5,6,7]