אתגר תכנותי: איסוף ערכי המקסימום בתוך חלון הזזה Sliding window maxima

תיאור האתגר התכנותית

בהינתן מערך של מספרים שלמים וחלון הזזה sliding window שאורכו קבוע, מצא את האיבר המקסימלי בכל מיקום של החלון אשר מוזז לאורך המערך כשהוא נע משמאל לימין.

לדוגמה, נתון מערך `nums` וחלון באורך 3 מקומות:

nums = [1, 3, -1, -3, 5, 3, 6, 7]
K = 3

הפונקציה תחזיר מערך:

[3, 3, 5, 5, 6, 7]

הסבר:

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

לדוגמה, בהינתן מערך `nums` וחלון באורך 3 מקומות:

nums = [1, 3, -1, -3, 5, 3, 6, 7]
K = 3

שלבי החישוב יהיו:

1. חלון ראשון (אינדקסים 0 עד 2): האיבר המקסימלי הוא 3, אז התוצאה עד כה היא [3].
2. חלון שני (אינדקסים 1 עד 3): האיבר המקסימלי נשאר 3, אז התוצאה עד כה היא [3, 3].
3. חלון שלישי (אינדקסים 2 עד 4): האיבר המקסימלי הוא 5, אז התוצאה עד כה היא [5, 3, 3].
4. נמשיך באותו אופן עד סוף המערך.

התוצאה הסופית תהיה:

 [3, 3, 5, 5, 6, 7]

פתרון יעיל במיוחד באמצעות deque

את השאלה אפשר לפתור בכל מיני דרכים, לדוגמה לולאה מקוננת (אומנם הכי קל לחשוב על הפתרון אבל הוא לא הכי יעיל), או בעזרת max-heap היעיל יותר. פה אני רוצה להשתמש במבנה של deque שהשימוש בו נותן את התוצאה היעילה ביותר.

deque - Double ended queue

בשפת התכנות פייתון deque, תור דו כיווני, הוא מבנה נתונים אשר משלב את היכולות של stack ושל queue. כאשר ב-stack (ערימה) פריטים מתווספים ומוסרים מראש הערימה. בדומה לערימה של צלחות כאשר הצלחת האחרונה שנערמה היא הראשונה שמוסרת. לעומת זאת ב-queue (תור) הפריטים מתווספים לסוף התור ומוסרים מתחילתו. בדומה לתור בחנות כאשר הראשון לעמוד בתור הוא גם הראשון לקבל שירות. הוספה והסרה של פריטים מתחילת ה-deque ומסופו דורשת זמן ביצוע ליניארי O(1) הכי יעיל שאפשר.

בשביל להשתמש ב-deque בפייתון נייבא אותו מהספרייה הסטנדרטית:

from collections import deque

אפשר להשתמש ב-deque כ-queue:

# Queue behavior
queue = deque()
queue.append(1)  # enqueue (add to the back)
queue.append(2)
queue.append(3)
print(queue.popleft())  # dequeue (remove from the front)  # Output: 1

אפשר להשתמש ב-deque כ-stack:

# Stack behavior
stack = deque()
stack.append(1)  # push (add to the front/top)
stack.append(2)
stack.append(3)
print(stack.pop())  # pop (remove from the front/top)  # Output: 3

הפתרון הבא לאיסוף ערכי המקסימום בתוך sliding window משתמש ב-deque גם כ-queue וגם כ-stack:

from collections import deque

def find_maxima_in_sliding_window(nums, k):
   # Goal: list maxima of numbers collected from sliding window with length k
   output = []
  
   # Sanitize   
   if not nums or k < 1:
       # Handle empty list or zero window size
       return []
  
   # Double-ended queue to store the indices of potential maximum items
   deq = deque()
  
   # Iterate over all the array items
   for idx, num in enumerate(nums):
      
       # Remove smaller elements from the deque's end to maintain max candidates
       while deq and num > nums[deq[-1]]:
           deq.pop()
          
       # Remove from front of deq index that has fallen outside the advancing window
       if deq and idx - k >= deq[0]:
           deq.popleft()
          
       # Add current index to deq for potential consideration in future windows
       deq.append(idx)
      
       # Record the maximum from the current window
       if idx >= k-1:
           # The front of the deque holds the max index
           output.append(nums[deq[0]])
          
   return output

נבדוק:

# Test cases  

# Different sizes of windows with length of k
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(find_maxima_in_sliding_window(nums, k)) # [3, 3, 5, 5, 6, 7]

nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 2
print(find_maxima_in_sliding_window(nums, k)) # [3, 3, -1, 5, 5, 6, 7]

nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 4
print(find_maxima_in_sliding_window(nums, k)) # [3, 5, 5, 6, 7]

# Array with equal items
nums = [1, 1, 1, 1, 1, 1, 1, 1]
k = 3
print(find_maxima_in_sliding_window(nums, k)) # [1, 1, 1, 1, 1, 1]

# Array and window size are the same
nums = [1, 3, -1]
k = 3
print(find_maxima_in_sliding_window(nums, k)) # [3]

# Empty array
nums = []
k = 3
print(find_maxima_in_sliding_window(nums, k)) # []

# 0 length window
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 0
print(find_maxima_in_sliding_window(nums, k)) # []

# Window size is larger than the array length
nums = [1, 3, -1, -3]
k = 5
print(find_maxima_in_sliding_window(nums, k))  # []

# Descending order array
nums = [7, 6, 5, 4, 3, 2, 1]
k = 3
print(find_maxima_in_sliding_window(nums, k))  # [7, 6, 5, 4, 3]

נסביר:

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

שלבי הפתרון כוללים:

הכנה:

• output : רשימה ריקה לאחסון המספרים המקסימליים שנמצא.
• deq : תור דו-כיווני, deque העוקב ביעילות אחר מספרים שיכולים להיות המקסימום בחלון שלנו.

הלולאה הראשית עוברת על כל מספר ברשימת הקלט:

• מסירים מהקצה האחורי של deq מספרים קטנים יותר מהמספר הנוכחי כי הם לא יכולים להיות מקסימום.
• מסירים מספרים ישנים החורגים מאורך החלון.
• מוסיפים את האינדקס של המספר הנוכחי ל-deq כדי לבדוק בהמשך האם הוא מצביע על מקסימום.

מציאת ערכי המקסימום:

• לאחר שהחלון מגיע לגודלו המלא, אנחנו יכולים להתחיל למצוא את המקסימומים.
• המספר שנמצא בקדמת ה-deq הוא בהכרח המקסימום, ולכן אנחנו מוסיפים אותו לרשימת התוצאות (output).

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

ניתוח יעילות הקוד

• סיבוכיות זמן: O(N) - על כל מספר ברשימת הקלט, שאורכה N, מבצעים לכל היותר k פעולות הוספה ומחיקה לתור הדו כיווני. מכיוון ש-k הוא ערך קבוע כאשר משך הזמן של כל פעולה הוא קבוע כי זו תכונת ה-deque, סיבוכיות הזמן היא לינארית ביחס לאורך מערך הקלט.
• סיבוכיות מקום: O(N) - התורם המשמעותי ביותר לדרישה נוספת של מקום בזיכרון הוא מערך הפלט output אשר אורכו לכל היותר N מספרים, בהתאם לאורך מערך הקלט.

מדריכים נוספים שעשויים לעניין אותך

stacks, ערימות וחידות

תורים Queues - הבנה ויישום בפייתון

Linked list - רשימה מקושרת - תיאוריה, קוד ואתגרים תכנותיים

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים