שיעור 7: חלון מחליק

דמיין/י מסגרת קטנה שזזה על פני שורת פריטים ומראה רק כמה מהם בכל פעם: כשהיא זזה ימינה, פריט אחד יוצא ואחד נכנס, ורוב מה שבפנים נשאר. זה 'חלון מחליק' (sliding window). במקום לסכם כל מסגרת מחדש (O(n·k), איטי), פשוט מוסיפים את מה שנכנס ומחסירים את מה שיצא — מעבר יחיד ומהיר, O(n).

חלון מחליק זה כמו להסתכל מבעד לחלון של רכבת נוסעת: בכל רגע רואים כמעט אותו נוף, רק שעץ אחד נעלם בצד אחד ועץ חדש מופיע בצד השני. לא צריך להביט שוב על כל הנוף מההתחלה — רק לשים לב למה שיצא ולמה שנכנס.

חלון מחליק: דפוס שבו טווח רציף נע על מערך, ומעדכן תוצאה מצטברת בהוספת האיבר הנכנס והחסרת היוצא — במקום לחשב כל חלון מחדש.
חלון בגודל קבוע: חלון מחליק שאורכו k נשאר קבוע: כל צעד מוסיף איבר אחד ומסיר איבר אחד.
חלון בגודל משתנה: חלון מחליק שגבולותיו מתרחבים ומתכווצים לפי תנאי (למשל סכום מינימלי), ולא לפי אורך קבוע מראש.