Trapping Rain Water

Q: מהי סיבוכיות הזמן של בעיית לכידת מי הגשמים?

פתרון שני המצביעים רץ בזמן O(n) ומשתמש ב־ O(1) מקום נוסף: בכל צעד מזיזים מצביע אחד פנימה, ולכן יש n-1 צעדים. הגרסה עם מערכי leftMax ו־ rightMax רצה גם היא בזמן O(n) , אבל משתמשת ב־ O(n) מקום. סריקת שני הצדדים מכל עמוד היא O(n²) , בערך 4 × 10^8 קריאות עבור 2 × 10^4 עמודים.

Q: למה פתרון שני המצביעים יכול להזיז את הצד הקצר יותר?

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

Q: האם אפשר לפתור את בעיית לכידת מי הגשם באמצעות מחסנית?

כן. החזק מחסנית של אינדקסים שגובהם יורד מלמטה למעלה. כשמגיע עמוד שגובהו גדול מזה של העליון, הוצא את העליון: הוא הרצפה של בריכה שקירותיה הם האיבר החדש בראש המחסנית והעמוד הנוכחי. הוסף (min(two walls) - floor) × (distance between the walls - 1) , והמשך להוציא איברים כל עוד העמוד הנוכחי גבוה מהם. המחסנית ממלאת את המים בשכבות אופקיות במקום בעמודות, בזמן O(n) ובמקום O(n) .

Q: במה שונה Trapping Rain Water מ־Container With Most Water?

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

קשהשני מצביעים מחסנית מונוטונית

+10

שורה של עמודות ניצבת זו לצד זו, רוחב כל אחת מהן יחידה אחת: height[i] הוא הגובה של עמודה i. גשם יורד על השורה ונאגר בשקעים שבין העמודות. מים נשארים מעל עמודה רק אם יש עמודה גבוהה יותר משמאל לה וגם עמודה גבוהה יותר מימין לה; מעבר לעמודה הראשונה והאחרונה הם זורמים החוצה.

החזירו את המספר הכולל של ריבועי יחידה של מים שהשורה מכילה.

פונקציה

trap(height: integer-array) → integer

heightinteger-array: הגובה של כל עמודה, משמאל לימין
מחזירהinteger: כמות יחידות המים הכוללת שנלכדה

אילוצים

1 ≤ height.length ≤ 2 × 10⁴
0 ≤ height[i] ≤ 10⁵
כל עמודה היא ברוחב יחידה אחת, והמים אינם נשארים מעבר לעמודה הראשונה או האחרונה.

דוגמאות

קלט: height = [0, 3, 1, 0, 2, 5, 1, 2]
פלט: 7
הסבר: בין ה־3 ל־5 המים עולים לגובה 3: הם מכילים 2 יחידות מעל העמודה בגובה 1, 3 מעל זו שבגובה 0 ו־1 מעל זו שבגובה 2. ה־1 שליד הסוף נמצא בין 5 ל־2, לכן הגובה שלו הוא 2 והוא מכיל יחידה אחת. 2 + 3 + 1 + 1 = 7.

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

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

סרוק את שני הצדדים של כל תיבה

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

האינטואיציה

חשבו את המים עמודה אחר עמודה. המים מעל העמודה i עולים עד שהם יגלשו מעל הנמוכה מבין שתי הדפנות שלה. הדופן השמאלית היא העמודה הגבוהה ביותר בכל מקום מאינדקס 0 עד i; הדופן הימנית היא העמודה הגבוהה ביותר מ-i ועד הסוף. לכן המפלס הוא min(leftMax, rightMax), וכמות המים מעל העמודה i היא המפלס פחות height[i].

ניקח את [0, 3, 1, 0, 2, 5, 1, 2] ואת העמודה שגובהה 0 באינדקס 3. העמודה הגבוהה ביותר משמאלה היא בגובה 3, ומימינה — בגובה 5. המפלס הוא 3, ולכן מצטברות שם 3 יחידות מים. עבור העמודה שגובהה 1 באינדקס 6, הדפנות הן בגובה 5 ובגובה 2: המפלס הוא 2, והיא מכילה יחידת מים אחת.

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

הבעיה היא העלות. עבור כל עמודה עוברים על כל השורה, חצי משמאל וחצי מימין, ולכן בסך הכול יש n × n קריאות: 4 × 10^8 עבור 2 × 10^4 עמודות. הסריקות גם חוזרות על אותן פעולות: העמודה הגבוהה ביותר משמאל לאינדקס 5 היא העמודה הגבוהה ביותר משמאל לאינדקס 4, בתוספת השוואה אחת, ואילו כוח גס מחשב אותה מחדש מאפס.

אלגוריתם

הגדר את water ל־0.
עבור כל אינדקס i, סרוק מ־0 עד i כדי למצוא את leftMax.
סרוק מ־i עד האינדקס האחרון כדי למצוא את rightMax.
הוסף את min(leftMax, rightMax) - height[i] אל water.
החזר את water.

def trap(height):
    n = len(height)
    water = 0
    for i in range(n):
        # The tallest bar at or left of i, and the tallest at or right of i.
        left_max = 0
        for j in range(i + 1):
            left_max = max(left_max, height[j])
        right_max = 0
        for j in range(i, n):
            right_max = max(right_max, height[j])
        water += min(left_max, right_max) - height[i]
    return water

חשבו מראש את העמודה הגבוהה ביותר בכל צד

האינטואיציה

הנוסחה נשארת; רק הדרך שבה מוצאים את שני הקירות משתנה. העמודה הגבוהה ביותר מ־0 עד i היא הגבוהה מבין העמודה הגבוהה ביותר מ־0 עד i-1 ו־height[i]. לכן, מעבר אחד משמאל לימין ממלא מערך leftMax, שכל איבר בו נבנה על סמך האיבר שקדם לו. מעבר אחד מימין לשמאל ממלא את rightMax באותו אופן. מעבר שלישי מחבר את min(leftMax[i], rightMax[i]) - height[i] עבור כל עמודה.

עבור [0, 3, 1, 0, 2, 5, 1, 2]: leftMax = [0, 3, 3, 3, 3, 5, 5, 5] ו־rightMax = [5, 5, 5, 5, 5, 5, 2, 2]. הערכים הקטנים מבין כל זוג הם הרמות [0, 3, 3, 3, 3, 5, 2, 2]. מחסרים את הגבהים ומקבלים [0, 0, 2, 3, 1, 0, 1, 0], שסכומם 7.

בכל מעבר נוגעים בכל עמודה פעם אחת, ולכן זמן הריצה הוא O(n): כ־6 × 10^4 צעדים עבור 2 × 10^4 עמודות, במקום 4 × 10^8. המחיר הוא שני מערכים נוספים של n מספרים. זו הגרסה שכדאי להתחיל איתה בריאיון: קשה לטעות בה, והגישה הבאה נועדה להסיר את המערכים, לא להציג רעיון אחר.

אלגוריתם

מלאו את leftMax משמאל לימין: leftMax[0] = height[0], ואז leftMax[i] = max(leftMax[i-1], height[i]).
מלאו את rightMax מימין לשמאל: rightMax[n-1] = height[n-1], ואז rightMax[i] = max(rightMax[i+1], height[i]).
עבור כל אינדקס, הוסיפו לסכום הכולל את min(leftMax[i], rightMax[i]) - height[i].
החזירו את הסכום הכולל.

def trap(height):
    n = len(height)
    left_max = [0] * n   # tallest bar from index 0 to i
    right_max = [0] * n  # tallest bar from index i to n-1
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])
    right_max[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])
    water = 0
    for i in range(n):
        water += min(left_max[i], right_max[i]) - height[i]
    return water

שני מצביעים שמזיזים את הצד התחתון

האינטואיציה

הנוסחה צריכה רק את הנמוכה מבין שתי הדפנות. אם אפשר להוכיח שהדופן השמאלית היא הנמוכה יותר באינדקס כלשהו, אין צורך כלל בדופן הימנית באותו אינדקס. שני מצביעים מאפשרים להוכיח זאת. הצב את left באינדקס 0 ואת right באינדקס האחרון, ושמור את leftMax ואת rightMax, העמודה הגבוהה ביותר שכל מצביע עבר עד כה, כולל העמודה שעליה הוא עומד.

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

כעת נניח ש-height[left] < height[right]. לפי האינווריאנט, leftMax קטן או שווה ל-height[right], ו-height[right] היא בעצמה עמודה שנמצאת מימין ל-left. לכן הדופן הימנית האמיתית של left גבוהה לפחות כמו leftMax, והמפלס ב-left הוא בדיוק leftMax, בלי קשר למה שנמצא בין המצביעים. הוסף את leftMax - height[left] והזז את left צעד אחד ימינה. כאשר height[right] היא העמודה הנמוכה יותר או שווה בגובהה, בצע את הפעולה ההפוכה בצד ימין. עדכן את המקסימום המצטבר לפני הוספת המים, כך שהעמודה שמתחת למצביע תיחשב כדופן של עצמה וכמות המים לעולם לא תהיה שלילית.

נעבור על [0, 3, 1, 0, 2, 5, 1, 2]. המצביעים מתחילים ב-0 וב-2: השמאלית נמוכה יותר, והיא מחזיקה 0. לאחר מכן 3 מול 2: הימנית נמוכה יותר, rightMax הופך ל-2, והיא מחזיקה 0. אחר כך 3 מול 1: הימנית שוב נמוכה יותר, וה-1 מחזיקה 2-1 = 1. אחר כך 3 מול 5: כעת השמאלית נמוכה יותר, leftMax הוא 3, ה-3 מחזיקה 0, ה-1 מחזיקה 2, ה-0 מחזיקה 3 וה-2 מחזיקה 1. המצביעים נפגשים ב-5. הסכום הכולל הוא 1 + 2 + 3 + 1 = 7, במעבר אחד ועם ארבעה משתנים.

אלגוריתם

אתחלו את left = 0, את right = n-1, ואת leftMax, rightMax ו-water ל-0.
כל עוד left < right, השוו בין height[left] לבין height[right].
אם העמודה השמאלית נמוכה יותר, הגדילו את leftMax ל-height[left] אם צריך, הוסיפו את leftMax - height[left] והזיזו את left ימינה.
אחרת, הגדילו את rightMax ל-height[right] אם צריך, הוסיפו את rightMax - height[right] והזיזו את right שמאלה.
החזירו את water כשהמצביעים נפגשים; העמודה שהם נפגשים בה היא הגבוהה ביותר ואינה מחזיקה מים.

def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = 0  # tallest bar passed so far from each end
    water = 0
    while left < right:
        if height[left] < height[right]:
            # A bar taller than height[left] waits on the right, so left_max sets the level here.
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            # A bar at least as tall as height[right] waits on the left, so right_max sets the level.
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1
    return water

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

הנוסחה קצרה, ורוב התשובות השגויות נובעות מסדר שגוי של שתי שורות או מהצד שאליו מזיזים.

הוספת המים לפני עדכון המקסימום הנוכחי. אם height[left] גבוה מ-leftMax, אז leftMax - height[left] הוא שלילי והסכום קטן. קודם עדכנו את המקסימום, ואז הוסיפו.
הזזת המצביע שעל המוט הגבוה יותר. הגובה ידוע רק בצד הנמוך יותר; הזזת הצד הגבוה יותר מסתמכת על קיר שלא הוכחתם שקיים. עבור [4, 1, 3, 0, 5] הגרסה הזאת מחזירה 4 במקום 8.
התחשבות בשכנים הקרובים בלבד. הקירות של מוט יכולים להיות רחוקים: ב-[3, 0, 2, 0, 1, 0, 4] המוט שגובהו 1 מחזיק מים עד לגובה 3, שנקבע על ידי מוטות המרוחקים ממנו ארבעה ושני צעדים. התשובה שם היא 12.
התייחסות לקצוות המערך כאל קירות. מים שמעבר למוט הראשון או האחרון נשפכים, ולכן מוט אחד, שני מוטות, או שורה שרק עולה או רק יורדת, מחזיקים 0.
החרגת המוט i מסריקותיו שלו בכוח גס. במקרה כזה, מוט שגבוה משני הצדדים יקבל כמות שלילית. כללו אותו, או הגבילו את התוצאה ל-0.
גלישת מספרים בגרסה שמבצעת כפל. כאן התשובה מגיעה לכ-2 × 10^9 (שני מוטות בגובה 10^5 מסביב ל-19,998 תאים ריקים), ועדיין נכנסת למספר שלם חתום של 32 סיביות; בגרסאות משלכם, השתמשו בסכומים של 64 סיביות.

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

מהי סיבוכיות הזמן של בעיית לכידת מי הגשמים?

פתרון שני המצביעים רץ בזמן O(n) ומשתמש ב־O(1) מקום נוסף: בכל צעד מזיזים מצביע אחד פנימה, ולכן יש n-1 צעדים. הגרסה עם מערכי leftMax ו־rightMax רצה גם היא בזמן O(n), אבל משתמשת ב־O(n) מקום. סריקת שני הצדדים מכל עמוד היא O(n²), בערך 4 × 10^8 קריאות עבור 2 × 10^4 עמודים.

למה פתרון שני המצביעים יכול להזיז את הצד הקצר יותר?

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

האם אפשר לפתור את בעיית לכידת מי הגשם באמצעות מחסנית?

כן. החזק מחסנית של אינדקסים שגובהם יורד מלמטה למעלה. כשמגיע עמוד שגובהו גדול מזה של העליון, הוצא את העליון: הוא הרצפה של בריכה שקירותיה הם האיבר החדש בראש המחסנית והעמוד הנוכחי. הוסף (min(two walls) - floor) × (distance between the walls - 1), והמשך להוציא איברים כל עוד העמוד הנוכחי גבוה מהם. המחסנית ממלאת את המים בשכבות אופקיות במקום בעמודות, בזמן O(n) ובמקום O(n).

במה שונה Trapping Rain Water מ־Container With Most Water?

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

Python

def trap(height):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

height = [0, 3, 1, 0, 2, 5, 1, 2]

צפוי

Trapping Rain Water

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

סרוק את שני הצדדים של כל תיבה

חשבו מראש את העמודה הגבוהה ביותר בכל צד

שני מצביעים שמזיזים את הצד התחתון

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

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

בעיות דומות