Sliding Window Maximum

Q: מהי סיבוכיות הזמן של מקסימום בחלון הזזה?

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

קשהחלון נע מחסנית מונוטונית תור

+10

נתון לך מערך של מספרים שלמים nums וגודל חלון k. חלון מכסה k ערכים עוקבים. הוא מתחיל בקצה השמאלי של המערך ומתקדם בכל פעם מיקום אחד ימינה, עד שהקצה הימני שלו נמצא מעל הערך האחרון.

החזר מערך שבו הערך הגדול ביותר בתוך החלון מופיע בכל אחד ממיקומיו, משמאל לימין. במערך באורך n יש n-k+1 חלונות, ולכן התוצאה מכילה n-k+1 ערכים.

פונקציה

maxSlidingWindow(nums: integer-array, k: integer) → integer-array

numsinteger-array: המערך שהחלון מחליק מעליו
kinteger: מספר הערכים בכל חלון
מחזירהinteger-array: הערך הגדול ביותר בכל חלון, מהחלון השמאלי ביותר ועד לחלון הימני ביותר

אילוצים

1 ≤ k ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
התוצאה מכילה nums.length-k+1 ערכים, אחד לכל חלון, לפי הסדר משמאל לימין.

דוגמאות

קלט: nums = [4, 2, 12, 3, 8, 5, 1]k = 3
פלט: [12, 12, 12, 8, 8]
הסבר: 12 נמצא בתוך שלושת החלונות הראשונים, [4, 2, 12], [2, 12, 3] ו-[12, 3, 8]. אחרי שהוא יוצא, בחלונות [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 אינו מוסיף תשובה שנייה.

+15 בדיקות נסתרות בשליחה

שאלת המשך

האם תוכל לבנות תור שתומך בהוספת ערך לסוף, בהסרת הערך מההתחלה ובקריאת הערך המרבי הנוכחי שלו, כל פעולה בזמן O(1) אמורטי?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

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

סרקו כל חלון

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

הרעיון הישיר ביותר נובע מההגדרה. החלון שמתחיל באינדקס start מכסה את הטווח מ־start עד start+k-1. קוראים את k הערכים האלה, שומרים את הגדול ביותר ומזיזים את נקודת ההתחלה צעד אחד ימינה. יש n-k+1 נקודות התחלה, מ־0 עד n-k.

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

הפתרון איטי. כל אחד מ־n-k+1 החלונות דורש k קריאות, והמכפלה היא הגדולה ביותר כאשר k הוא בערך מחצית מ־n. עבור n = 2 × 10^4 ו־k = 10^4, מדובר ב־10^4 חלונות של 10^4 ערכים, כלומר 10^8 קריאות. גרוע מכך, שני חלונות סמוכים חולקים k-1 ערכים, ולכן כמעט כל קריאה חוזרת על קריאה שכבר ביצעת.

אלגוריתם

צרו רשימת תוצאות ריקה.
עברו בלולאה על start מ־0 עד n-k.
הגדירו את best בתור nums[start], ואז השוו אותו לכל ערך עד nums[start+k-1] והשאירו את הגדול יותר.
הוסיפו את best לתוצאות.
החזירו את התוצאות.

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, וכן הלאה, עם בלוק אחרון קצר יותר אם n אינו כפולה של k. חלון הוא באורך של בדיוק k, ולכן הוא או תואם לבלוק אחד או מכסה את סוף הבלוק האחד ואת תחילת הבלוק הבא. הוא לעולם אינו נוגע בשלושה בלוקים.

מכאן נובעים שני מערכים. fromStart[i] הוא הערך הגדול ביותר מתחילת הבלוק של i ועד i, וממלאים אותו משמאל לימין ומאפסים אותו בתחילת כל בלוק. toEnd[i] הוא הערך הגדול ביותר מ-i ועד סוף הבלוק שלו, וממלאים אותו מימין לשמאל ומאפסים אותו בסוף כל בלוק. החלון שמתחיל ב-i מסתיים ב-i+k-1. החלק השמאלי שלו מכוסה על ידי toEnd[i] והחלק הימני על ידי fromStart[i+k-1], ולכן המקסימום שלו הוא הגדול מבין השניים. כשהחלון הוא בלוק שלם, שני החלקים הם המקסימום של אותו בלוק, והתשובה עדיין נכונה.

עבור nums = [4, 2, 12, 3, 8, 5, 1] ו-k = 3, הבלוקים הם [4, 2, 12], [3, 8, 5] ו-[1]. fromStart הוא [4, 4, 12, 3, 8, 8, 1] ו-toEnd הוא [12, 12, 12, 8, 8, 5, 1]. החלון [2, 12, 3] מתחיל ב-1: toEnd[1] = 12 מכסה את 2 ואת 12, fromStart[3] = 3 מכסה את 3, והתשובה היא 12.

האלגוריתם פועל בזמן O(n), בשלושה מעברים על המערך. המחיר הוא שני מערכי עזר באורך n, ונדרש המערך כולו לפני שאפשר לחשב את התשובה עבור החלון הראשון.

אלגוריתם

מלאו את fromStart משמאל לימין: העתיקו את nums[i] כאשר i הוא כפולה של k, אחרת קחו את הגדול מבין fromStart[i-1] ו-nums[i].
מלאו את toEnd מימין לשמאל: העתיקו את nums[i] כאשר i הוא האינדקס האחרון או i+1 הוא כפולה של k, אחרת קחו את הגדול מבין toEnd[i+1] ו-nums[i].
עבור כל התחלה 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 מכיל גם את i, כי i נמצא ימינה יותר ויוצא מאוחר יותר. בכל החלונות האלה nums[i] גדול לפחות כמו nums[j], ולכן j לא יוכל להיות שוב המקסימום. ברגע ש-i מגיע, j חסר תועלת ואפשר לשכוח אותו.

נחזיק תור דו-קצותי של האינדקסים שלא שכחנו. כש-i מגיע, נוציא מהסוף אינדקסים כל עוד הערכים שלהם קטנים או שווים ל-nums[i], ואז נוסיף את i. לכן לערכים של האינדקסים שנותרו יש סדר יורד ממש מההתחלה לסוף, כי כל ערך ישן שלא היה גדול יותר היה מוצא מהתור. כך שההתחלה מכילה את הערך הגדול ביותר בחלון. התור הדו-קצותי שומר אינדקסים, ולא ערכים, כי גם האיבר שבתחילתו צריך לצאת כשהחלון חולף עליו: החלון שמסתיים ב-i מתחיל ב-i-k+1, ולכן האינדקס i-k הוא זה שיצא מהחלון, ואם הוא בתחילת התור, מסירים אותו.

נעבור על nums = [4, 2, 12, 3, 8, 5, 1] עם k = 3, ונרשום את הערכים שבתור הדו-קצותי. 4 נכנס: [4]. 2 קטן ממנו, ולכן הוא ממתין מאחוריו: [4, 2]. 12 מוציא את שניהם: [12], והתשובה לחלון הראשון היא 12. 3 ממתין: [12, 3], והתשובה היא 12. 8 מוציא את 3: [12, 8], והתשובה היא 12. 5 ממתין: [12, 8, 5], אבל 12 נמצא באינדקס 2, והחלון שמסתיים באינדקס 5 מתחיל באינדקס 3, ולכן 12 יצא מהחלון: [8, 5], והתשובה היא 8. 1 ממתין: [8, 5, 1], והתשובה היא 8.

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

אלגוריתם

צרו תור דו־צדדי ריק עבור אינדקסים ורשימת תוצאות ריקה.
עבור כל אינדקס i, הסירו אינדקסים מהקצה האחורי כל עוד התור הדו־צדדי אינו ריק והערך בקצה האחורי שלו קטן או שווה ל־nums[i].
הוסיפו את i בקצה האחורי.
אם האינדקס בקצה הקדמי שווה ל־i-k, הוא יצא מהחלון: הסירו אותו מהקצה הקדמי.
כאשר i ≥ k-1, חלון מלא מסתיים ב־i: הוסיפו את הערך שבאינדקס הקדמי לרשימת התוצאות.
החזירו את התוצאה.

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

מלכודות ומקרי קצה

רוב הבאגים נובעים מהגבולות של החלון או ממה שה-deque מאחסן.

אחסון ערכים במקום אינדקסים. לאחר מכן פג תוקפו של האיבר הראשון כשהוא שווה ל-nums[i-k], וכפילויות גורמות לבעיה. עם [3, 1, 3] ו-k = 2, ה-3 השני מוציא את הראשון, ואז הוא עצמו מוסר, כי הוא שווה לערך שיצא מהחלון. אחסנו אינדקסים והשוו את האיבר הראשון ל-i-k.
מתן התשובה מוקדם מדי או מאוחר מדי. החלון המלא הראשון מסתיים באינדקס k-1, ולא ב-k, והתוצאה חייבת להכיל בדיוק n-k+1 ערכים.
הסרת האינדקס הלא נכון. החלון שמסתיים ב-i מתחיל ב-i-k+1, לכן i-k הוא האינדקס שיוצא. הסרת i-k+1 מסירה ערך שעדיין נמצא בחלון.
קריאת האיבר האחרון או הראשון ב-deque ריק. בדקו שיש בו איבר לפני שאתם משווים לאיבר האחרון שלו.
התייחסות ל-deque כאל עותק של החלון. הוא מכיל רק את המועמדים, בין אינדקס אחד ל-k אינדקסים, ולכן הגודל שלו לא מלמד אתכם דבר על החלון.
בגישת הבלוקים, שכחה שהבלוק האחרון עשוי להיות קצר מ-k. המעבר מימין לשמאל חייב להתחיל מחדש גם באינדקס האחרון וגם בסוף כל בלוק.

שאלות נפוצות4

מהי סיבוכיות הזמן של מקסימום בחלון הזזה?

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

האם אפשר לפתור את בעיית המקסימום בחלון הזזה באמצעות ערימה?

כן. דחפו זוגות של ערך ואינדקס לערמת מקסימום. לפני קריאת האיבר שבראש, הוציאו אותו כל עוד האינדקס שלו מחוץ לחלון, מכיוון שרשומות ישנות מוסרות רק כשהן מגיעות לראש. זה פועל בזמן O(n log n) ויכול להכיל עד n רשומות. התור הדו־צדדי מהיר וקטן יותר, כי הוא מסיר ערכים חסרי תועלת ברגע שמגיע ערך גדול יותר.

למה התור הדו־קצוות מאחסן אינדקסים ולא ערכים?

החזית חייבת לצאת כשהחלון עובר מעבר לה, ורק האינדקס שלה אומר לך זאת. עם הערכים בלבד תצטרך לנחש לפי nums[i-k], וזה נכשל כשאותו ערך מופיע יותר מפעם אחת. האינדקס גם נותן לך את הערך ללא עלות, בתור nums[index].

מה ההבדל בין תור דו־צדדי מונוטוני למחסנית מונוטונית?

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

Python

def maxSlidingWindow(nums, k):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

nums = [4, 2, 12, 3, 8, 5, 1]
k = 3

צפוי

[12, 12, 12, 8, 8]

Sliding Window Maximum

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

סרקו כל חלון

בלוקים עם ערכי מקסימום מכל צד

תור דו־צדדי מונוטוני של אינדקסים

מלכודות ומקרי קצה

שאלות נפוצות4

בעיות דומות