Sliding Window Maximum
ניתן לך מערך של מספרים שלמים nums וגודל חלון k. חלון של k ערכים רצופים מתחיל בקצה השמאלי ומתקדם ימינה, מיקום אחד בכל פעם, עד שהקצה הימני שלו מגיע לערך האחרון. החזר את הערך הגדול ביותר בחלון בכל מיקום, משמאל לימין: n-k+1 ערכים עבור מערך באורך n.
פונקציה
- numsinteger-array
- המערך שהחלון מחליק מעליו
- kinteger
- מספר הערכים בכל חלון
- מחזירהinteger-array
- הערך הגדול ביותר בכל חלון, מהחלון השמאלי ביותר ועד לחלון הימני ביותר
אילוצים
1 ≤ k ≤ nums.length ≤ 2 × 104-104 ≤ nums[i] ≤ 104- התוצאה מכילה
nums.length-k+1ערכים, אחד לכל חלון, לפי הסדר משמאל לימין.
דוגמאות
- קלט
- nums = [4, 2, 12, 3, 8, 5, 1]k = 3
- פלט
- [12, 12, 12, 8, 8]
- הסבר
- 12 נמצא בתוך שלושת החלונות הראשונים, ולכן כל אחד מהם מחזיר 12. לאחר שהוא יוצא בהחלקה, הערך הגדול ביותר גם ב-
[3, 8, 5]וגם ב-[8, 5, 1]הוא 8.
- קלט
- nums = [-3, -1, -7, -2]k = 2
- פלט
- [-1, -1, -2]
- הסבר
- החלונות הם
[-3, -1],[-1, -7]ו־[-7, -2]. הגדול מבין שני מספרים שליליים הוא זה שקרוב יותר לאפס, ולכן מתקבלים -1, -1 ו־-2.
- קלט
- nums = [6, 6, 1]k = 3
- פלט
- [6]
- הסבר
- כאשר
kשווה לאורך המערך, יש חלון אחד — המערך כולו. הערך הגדול ביותר בו הוא 6; העותק השני של 6 אינו מוסיף תשובה שנייה.
שאלת המשך
האם תוכל לבנות תור שתומך בהוספת ערך בסוף, בהסרת הערך בתחילתו ובקריאת הערך המרבי הנוכחי שלו, כל אחת מהפעולות בזמן אמורטי של O(1)?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
סריקת כל חלון כדי למצוא את הערך הגדול ביותר בו עולה
kצעדים לכל חלון. השוו בין שני חלונות שכנים: הם חולקיםk-1ערכים, כי ערך אחד יוצא משמאל ואחד נכנס מימין.כשערך חדש נכנס, כל ערך ישן יותר בחלון שקטן ממנו או שווה לו לא יוכל עוד להיות המקסימום. הערך החדש נשאר בכל חלון עתידי שעדיין מכיל את הערך הישן, והוא גדול ממנו או שווה לו. אפשר להשליך את הערכים הישנים האלה לצמיתות.
שמרו בתור דו־קצוות את האינדקסים של הערכים שנותרו, כך שערכיהם יהיו בסדר יורד ממש מהחזית לאחור. עבור כל אינדקס חדש, הוציאו מאחור ערכים קטנים ממנו או שווים לו, הוסיפו את האינדקס, הסירו את האיבר הקדמי אם הוא יצא מהחלון, וקראו את הערך המרבי בחלון מהחזית.
פתרון
חלונות סמוכים חולקים k-1 ערכים, ולכן חישוב מחדש של כל מקסימום חוזר על כמעט כל העבודה. אבל אי אפשר לבטל מקסימום: כשהערך הגדול ביותר יוצא מהחלון, צריך את הערך השני בגודלו בלי לקרוא שוב את החלון. תור דו־צדדי מונוטוני שומר רק את הערכים שעדיין עשויים להפוך למקסימום, והתשובה נמצאת בראשו.
סרוק כל חלון
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
קרא את ערכי k של כל חלון ושמור את הגדול ביותר. כל חלון נקרא במלואו, ולכן אי אפשר לפספס את הערך המרבי שלו. כל אחד מ־n-k+1 החלונות מצריך k קריאות; במקרה הגרוע, כאשר k הוא בערך חצי מ־n: n = 2 × 10^4 ו־k = 10^4 נותנים בערך 10^4 חלונות של 10^4 ערכים, כלומר 10^8 קריאות.
אלגוריתם
- עבור עם
startמ-0 עדn-k. - קח את הגדול ביותר מתוך
nums[start]עדnums[start+k-1]. - הוסף אותו לתוצאה, והחזר את התוצאה לאחר הלולאה.
def maxSlidingWindow(nums, k):
result = []
for start in range(len(nums) - k + 1):
# Read all k values of this window again
result.append(max(nums[i] for i in range(start, start + k)))
return resultבלוקים עם ערכי מקסימום מכל צד
האינטואיציה
חלקו את המערך לבלוקים בגודל k: האינדקסים 0 עד k-1, אחר כך k עד 2k-1, וכן הלאה, עם בלוק אחרון קצר יותר אם k אינו מחלק את n. חלון הוא בדיוק באורך k, ולכן הוא בלוק שלם אחד או סוף של בלוק אחד ותחילת הבלוק הבא.
לכן חשבו מראש את fromStart[i], הערך הגדול ביותר מתחילת הבלוק של i ועד i, ואת toEnd[i], הערך הגדול ביותר מ-i ועד סוף הבלוק שלו. החלון שמתחיל ב-i מסתיים ב-i+k-1: toEnd[i] מכסה את החלק השמאלי שלו ו-fromStart[i+k-1] את החלק הימני שלו, ולכן הגדול מביניהם הוא הערך המרבי שלו. בדוגמה הראשונה, החלון [2, 12, 3] משתמש ב-toEnd[1] = 12 וב-fromStart[3] = 3, ולכן התוצאה היא 12.
שלושה מעברים נותנים זמן O(n), במחיר של שני מערכי עזר באורך n ושל הצורך לקבל את המערך כולו לפני התשובה הראשונה.
אלגוריתם
- מלאו את
fromStartמשמאל לימין, והתחילו מחדש עםnums[i]כאשרiהוא כפולה שלk. - מלאו את
toEndמימין לשמאל, והתחילו מחדש עםnums[i]באינדקס האחרון ובכל מקום שבוi+1הוא כפולה שלk. - עבור כל ערך התחלה
iמ-0 עדn-k, הוסיפו את הגדול מביןtoEnd[i]ו-fromStart[i+k-1].
def maxSlidingWindow(nums, k):
n = len(nums)
# Cut nums into blocks of k: indices 0..k-1, k..2k-1, and so on.
from_start = [0] * n # max from the start of i's block up to i
to_end = [0] * n # max from i up to the end of i's block
for i in range(n):
if i % k == 0:
from_start[i] = nums[i]
else:
from_start[i] = max(from_start[i - 1], nums[i])
for i in range(n - 1, -1, -1):
if i == n - 1 or (i + 1) % k == 0:
to_end[i] = nums[i]
else:
to_end[i] = max(to_end[i + 1], nums[i])
# A window [i, i+k-1] is the tail of one block plus the head of the next.
return [max(to_end[i], from_start[i + k - 1]) for i in range(n - k + 1)]תור דו־קצותי מונוטוני של אינדקסים
האינטואיציה
אם האינדקס j מופיע לפני i ו-nums[j] ≤ nums[i], אז j לא יוכל להיות שוב מקסימום: כל חלון מאוחר יותר שמכיל את j מכיל גם את i, שיוצא ממנו מאוחר יותר. לכן, כש-i מגיע, אפשר לשכוח את j.
שומרים תור דו-כיווני של האינדקסים שעדיין לא נשכחו. כש-i מגיע, מוציאים מהקצה האחורי אינדקסים כל עוד הערכים שלהם קטנים או שווים ל-nums[i], ואז מוסיפים את i. הערכים שנותרים יורדים בקפדנות מהחזית לאחור, ולכן הערך בחזית הוא המקסימום בחלון. שומרים אינדקסים, כי גם האינדקס שבחזית צריך לצאת כשהחלון עובר אותו. בדוגמה הראשונה, באינדקס 5 התור הדו-כיווני מכיל את 12, 8 ו-5; 12 נמצא באינדקס 5 - 3 = 2, ולכן הוא יוצא והתשובה היא 8.
כל אינדקס מתווסף פעם אחת ומוסר לכל היותר פעם אחת: לכל היותר 2n פעולות בתור הדו-כיווני, בזמן O(n). התור הדו-כיווני לעולם אינו מכיל יותר מ-k אינדקסים.
אלגוריתם
- עבור כל אינדקס
i, הוצא אינדקסים מהקצה האחורי כל עוד התור הדו־כיווני אינו ריק והערך בקצה האחורי שלו קטן או שווה ל־nums[i]. - הוסף את
iבקצה האחורי. - אם האינדקס הקדמי שווה ל־
i-k, הוא יצא מהחלון: הוצא אותו. - ברגע ש־
i ≥ k-1, הוסף את הערך שבאינדקס הקדמי לתוצאה.
from collections import deque
def maxSlidingWindow(nums, k):
window = deque() # indices; their values strictly decrease from front to back
result = []
for i, x in enumerate(nums):
# A value at the back that is not bigger than x can never be a maximum again.
while window and nums[window[-1]] <= x:
window.pop()
window.append(i)
# The front index has slid out of the window on the left.
if window[0] == i - k:
window.popleft()
# From index k-1 on, every step completes a window; its maximum sits at the front.
if i >= k - 1:
result.append(nums[window[0]])
return result
מלכודות ומקרי קצה
- שמירת ערכים במקום אינדקסים. עם
[3, 1, 3]ו-k = 2, ה-3 השני מוציא את הראשון, ואז מוסר בעצמו כי הוא שווה ל-nums[0], הערך שיצא. - מתן התשובה מוקדם מדי או מאוחר מדי. החלון המלא הראשון מסתיים באינדקס
k-1, והתוצאה חייבת להכיל בדיוקn-k+1ערכים. - הוצאה של
i-k+1במקוםi-k. האינדקס הזה עדיין מצביע על הערך הראשון בחלון. - קריאה מהחלק האחורי של התור הדו-צדדי בלי לבדוק שיש בו משהו.
- בגישת הבלוקים, שכחה שהבלוק האחרון יכול להיות קצר מ-
k. המעבר מימין לשמאל חייב להתחיל מחדש גם באינדקס האחרון וגם בסוף כל בלוק.
שאלות נפוצות3
מהי סיבוכיות הזמן של מקסימום חלון נע?
פתרון התור הדו־צדדי המונוטוני פועל בזמן O(n), כי כל אינדקס נכנס לתור פעם אחת לכל היותר, ומוסר ממנו פעם אחת לכל היותר. התור מכיל לכל היותר k אינדקסים, ולכן המקום הנוסף הוא O(k), מעבר למקום הדרוש לתוצאה.
האם אפשר לפתור את בעיית המקסימום בחלון הזזה באמצעות ערימה?
כן. הכנס זוגות של ערכים ואינדקסים לערימת מקסימום, ולפני קריאת האיבר העליון, הוצא אותו כל עוד האינדקס שלו מחוץ לחלון. הפעולה מתבצעת בזמן O(n log n) ויכולה להכיל עד n איברים. התור הדו־צדדי מהיר וקטן יותר כי הוא מסיר ערכים חסרי תועלת ברגע שמגיע ערך גדול יותר.
מה ההבדל בין תור דו־קצוות מונוטוני למחסנית מונוטונית?
הקצה האחורי של הדק פועל כמו מחסנית מונוטונית: לפני שמכניסים ערך, מוציאים ממנה את הערכים שהוא הופך לחסרי תועלת. הדק מוסיף יציאה מהקצה הקדמי עבור ערכים ישנים מדי. לאיבר הגדול הבא אין תוקף, ולכן הוא דורש רק מחסנית. הפכו את ההשוואה, והדק יספק את המינימום בכל חלון.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def maxSlidingWindow(nums, k):
# כתבו כאן קודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנטים
nums = [4, 2, 12, 3, 8, 5, 1] k = 3
הפלט הצפוי
[12, 12, 12, 8, 8]