Container With Most Water
ניתנת לך רשימה height של מספרים שלמים לא שליליים. קו i הוא קיר אנכי בגובה height[i] הניצב במיקום i. כל שני קווים יוצרים מיכל עם הקרקע, והוא יכול להכיל כמות מים השווה לגובה הקו הנמוך מבין השניים כפול המרחק בין שני הקווים. הקווים האחרים אינם מפריעים. החזר את כמות המים המרבית שזוג יחיד של קווים יכול להכיל.
פונקציה
- heightinteger-array
- הגבהים של השורות במיקומים 0, 1, 2 וכן הלאה
- מחזירהinteger
- כמות המים המרבית ששתי שורות יכולות להכיל
אילוצים
2 ≤ height.length ≤ 1040 ≤ height[i] ≤ 104- התשובה היא לכל היותר 108, ולכן היא נכנסת למספר שלם בן 32 סיביות.
דוגמאות
- קלט
- height = [3, 7, 2, 5, 4, 7, 3, 6]
- פלט
- 36
- הסבר
- לשורות במיקומים 1 ו־7 יש גבהים 7 ו־6, והמרחק ביניהן הוא 6, ולכן הן מכילות 6 × 6 = 36. שתי השורות הגבוהות ביותר, שגובהן 7 במיקומים 1 ו־5, מכילות רק 7 × 4 = 28, והזוג החיצוני מכיל 3 × 7 = 21.
- קלט
- height = [4, 4]
- פלט
- 4
- הסבר
- שתי שורות יוצרות מיכל אחד בדיוק: גובה 4 ורוחב 1, ולכן הוא מכיל 4.
+15 בדיקות נסתרות בשליחה
שאלת המשך
כאן מתעלמים מהקווים שבין שני הקווים שתבחרו. אם כל הקווים היו במקום זאת עמודות מלאות, כמה מים היו נאספים ביניהם? תוכלו לחשב זאת גם ב־O(n)?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
התחילו בשני הקווים החיצוניים: הם יוצרים את המיכל הרחב ביותר. הזזה של אחד הקצוות פנימה מקטינה את הרוחב ביחידה אחת. איזה משני הקווים עשוי לפצות על כך?
המים מוגבלים על ידי הקו הקצר יותר. הזזת הקו הגבוה יותר פנימה משאירה את אותה מגבלה ומקטינה את הרוחב, ולכן היא לעולם לא יכולה לעזור. רק החלפת הקו הקצר יותר עשויה לעזור.
השאר מצביע בכל קצה. מדוד את המים שביניהם ושמור את הערך הטוב ביותר, ואז הזז את המצביע שבצד הקו הקצר יותר צעד אחד פנימה. עצור כשהמצביעים נפגשים.
פתרון
יש בערך n²/2 זוגות של קווים, ולכן עבור 10^4 קווים, בדיקת כולם משמעותה 5 × 10^7 מכפלות. הפתרון הוא שכמות המים תלויה רק בקו הקצר יותר בזוג: ברגע שיודעים שקו הוא הצד הקצר יותר במכל הרחב ביותר שהוא עדיין יכול ליצור, אף מכל צר יותר שמשתמש בו לא יוכל להניב תוצאה טובה יותר. שתי מצביעות הופכות את העובדה הזאת למעבר אחד משני הקצוות.
בדוק כל זוג
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
כל מכל הוא זוג של מיקומים i < j. המים עולים עד שהם נשפכים מעל הקיר הנמוך יותר, והרצפה בין הקירות היא ברוחב j - i, ולכן הזוג מכיל min(height[i], height[j]) × (j - i). נסו כל זוג, שמרו את הגדול ביותר, וכך תקבלו את התשובה לפי ההגדרה.
הבעיה היא מספר הזוגות. n קווים יוצרים n(n-1)/2 זוגות: בערך 5 × 10^7 עבור 10^4 קווים, ופי ארבעה בכל פעם שמכפילים את גודל הרשימה. שפה מקומפלת תבצע זאת בשבריר שנייה, אבל Python, Ruby או R זקוקות לשניות רבות, והמספר גדל מהר מדי עבור כל שפה ברגע ש-n מגיע ל-10^5.
אלגוריתם
- הגדר את
bestל־0. - עבור כל
i, ועבור כלjשאחריו, חשב אתmin(height[i], height[j]) × (j - i). - שמור את הגדול מבין
bestלבין הערך הזה. - החזר את
best.
def maxArea(height):
n = len(height)
best = 0
for i in range(n):
for j in range(i + 1, n):
water = min(height[i], height[j]) * (j - i)
best = max(best, water)
return bestהשורות הגבוהות ביותר תחילה
האינטואיציה
הסתכלו על מיכל מהצד של הצלע הקצרה שלו. אם הצלע הקצרה היא קו i, כמות המים היא height[i] כפול המרחק, והצלע השנייה יכולה להיות כל קו שגובהו לפחות זהה. לכן, המיכל הטוב ביותר שבו i היא הצלע הקצרה מחבר אותה לקו הרחוק ביותר שגובהו לפחות זהה.
כדי למצוא את הצלעות המתאימות במהירות, סדרו את הקווים מהגבוה ביותר לנמוך ביותר. כשמגיע תורו של קו i, כל קו שסודר לפניו גבוה לפחות כמוהו, והרחוק ביותר מביניהם נמצא באינדקס השמאלי ביותר או הימני ביותר שכבר סודר. עקבו אחר שני האינדקסים האלה, lo ו-hi, וקו i יכול להכיל לכל היותר height[i] × max(i - lo, hi - i). התשובה היא הגדול מבין הערכים האלה, כי המיכל הטוב ביותר נספר כשמגיע תורו של הקו הנמוך יותר שלו.
בדוגמה הראשונה, שני הקווים שגובהם 7, במיקומים 1 ו-5, מגיעים ראשונים ומכילים 28. הקו שגובהו 6 במיקום 7 מגיע אחריהם, עם lo = 1 ו-hi = 5, ומכיל 6 × 6 = 36. אף קו נמוך יותר לא מניב תוצאה טובה יותר. קווים בגובה שווה יכולים להגיע בכל סדר: מבין שני קווים שגובהם שווה, הקו שמגיע שני רואה בראשון שותף אפשרי.
המיון דורש O(n log n) והמעבר דורש O(n), וזה מהיר מספיק. עם זאת, עדיין נדרש זיכרון O(n) לשמירת הסדר, והגישה הבאה מוותרת גם על המיון וגם על הזיכרון.
אלגוריתם
- מיינו את האינדקסים לפי גובה, מהגבוה לנמוך.
- הגדירו את
loואתhiכאינדקס הראשון בסדר הזה, ואתbestכ־0. - עבור כל אינדקס הבא
i, חשבו אתheight[i]כפול הגדול מביןi - loו־hi - i, ושמרו את הערך הטוב ביותר. - עדכנו את
loואתhiכך שיכללו אתi. - החזירו את
best.
def maxArea(height):
# Indices from the tallest line to the shortest.
order = sorted(range(len(height)), key=lambda i: height[i], reverse=True)
lo = hi = order[0] # leftmost and rightmost index among the lines placed so far
best = 0
for i in order[1:]:
# Every placed line is at least as tall as line i, so line i is the
# shorter side, and its best partner is the placed line farthest away.
best = max(best, height[i] * max(i - lo, hi - i))
lo = min(lo, i)
hi = max(hi, i)
return bestשני מצביעים משני הקצוות
האינטואיציה
התחל מהמכל הרחב ביותר, left = 0 ו-right = n-1, ומדוד אותו. עכשיו אפשר לוותר על אחד משני הקווים, והבחירה מוכתבת: הסר את הקו הקצר יותר. נניח ש-height[left] ≤ height[right]. כל מכל אחר שמשתמש בקו left מצמיד אותו לקו קרוב יותר מ-right, ולכן הוא צר יותר, והגובה שלו עדיין לכל היותר height[left]. אף אחד מהם לא מכיל יותר מים מהמכל שמדדת, ולכן סיימנו עם הקו left ו-left מתקדם צעד אחד ימינה. אם נזיז במקום זאת את הקו הגבוה יותר, תקרת הגובה תישאר זהה והרוחב יקטן, ולכן התוצאה יכולה רק להיות גרועה יותר. כאשר שני הגבהים שווים, סיימנו עם שני הקווים, ולא משנה איזה מהם נזיז.
בכל צעד מסירים קו אחד לצמיתות, ולכן אחרי n-1 צעדים המצביעים נפגשים. לעולם לא מדלגים על הזוג הטוב ביותר: בפעם הראשונה שמסירים אחד משני הקווים שלו, המכל שנמדד באותו רגע מכיל לפחות אותה כמות מים.
ב-[3, 7, 2, 5, 4, 7, 3, 6], המיקומים 0 ו-7 מכילים 3 × 7 = 21. ה-3 קצר יותר, ולכן left מתקדם למיקום 1. המיקומים 1 ו-7 מכילים 6 × 6 = 36, וכעת ה-6 קצר יותר, ולכן right מתקדם למיקום 6. המכלים הבאים מכילים 15, 28, 12, 10 ו-2, ולכן התשובה נשארת 36.
אלגוריתם
- אתחל את
left = 0, אתright = n-1ואתbest = 0. - כל עוד
left < right, חשב אתmin(height[left], height[right]) × (right - left)ושמור את הערך הטוב ביותר. - אם
height[left] < height[right], הזז אתleftצעד אחד ימינה. אחרת, הזז אתrightצעד אחד שמאלה. - כשהמצביעים נפגשים, החזר את
best.
def maxArea(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
water = min(height[left], height[right]) * (right - left)
best = max(best, water)
# The shorter line cannot do better with any line closer in, so drop it.
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
מלכודות ומקרי קצה
הלולאה עם שני המצביעים קצרה, לכן הטעויות נמצאות בפרטים.
- הזזת הקו הגבוה יותר. בדוגמה הראשונה, שמחזירה 21 במקום 36: ה־6 במיקום 7 הוא הקו הגבוה יותר בזוג הראשון, ולכן הוא יוצא לפני שהוא בכלל פוגש את ה־7 במיקום 1.
- שימוש בקו הגבוה יותר, או בממוצע של שניהם, בתור הגובה. המים נשפכים מעל הדופן הנמוכה יותר, לכן הגובה הוא המינימום.
- טעות של יחידה אחת בחישוב הרוחב. הקווים במיקומים
iו־jנמצאים במרחקj - i, ולאj - i + 1, ולכן שני קווים סמוכים מכילים כמות מים השווה לגובה הנמוך יותר שלהם כפול 1. - הנחה שהתשובה מתקבלת מהקו הגבוה ביותר או מהזוג החיצוני. בדוגמה הראשונה, שני הקווים שגובהם 7 מכילים 28, והזוג החיצוני מכיל 21, בעוד שהתשובה היא 36.
- גלישה עם גבולות גדולים יותר. כאן המים נשארים מתחת ל־10^8, אבל כשגם הגבהים וגם האורכים קרובים ל־10^5, המכפלה עוברת את 2^31 ונדרש מספר שלם של 64 סיביות.
שאלות נפוצות4
מהי סיבוכיות הזמן של Container With Most Water?
הפתרון באמצעות שני מצביעים פועל בזמן O(n) ומשתמש ב-O(1) מקום נוסף. בכל צעד מזיזים מצביע אחד עמדה אחת פנימה, ולכן יש לכל היותר n-1 צעדים. בדיקת כל זוג אורכת O(n²), ומיון הקווים לפי גובה אורך O(n log n).
למה להזיז את המצביע לקו הקצר יותר?
גובה המים מוגבל על ידי הקו הקצר יותר. לכל מכל אחר ששומר על אותו קו יש קו מקביל קרוב יותר פנימה, ולכן הוא צר יותר ואינו גבוה יותר מהקו הקצר יותר. אף אחד מהם לא יכול להתעלות על המכל שמדדת, ולכן אפשר לוותר על הקו הקצר יותר בלי לאבד את התשובה.
האם "Container With Most Water" היא בעיה חמדנית?
כן. בכל שלב מתקבלת בחירה מקומית שלא מבוטלת לעולם, ומסירים את הקו הקצר יותר. הבחירה בטוחה כי כל מיכל שהשלב שולל אינו טוב יותר ממיכל שכבר נמדד. לכן הבעיה מסווגת גם תחת חמדנות וגם תחת שתי מצביעות.
במה שונה Container With Most Water מ־Trapping Rain Water?
כאן חשובות רק שתי השורות שנבחרו, ומתעלמים מהשורות שביניהן, ולכן התשובה היא מלבן יחיד. בבעיית Trapping Rain Water כל עמודה מלאה, והמים מצטברים מעל כל עמודה עד לגובה הנמוך מבין העמודות הגבוהות ביותר שמשני צדדיה, ולכן התשובה היא סכום על פני כל המיקומים. לשתי הבעיות יש פתרונות בשיטת שני מצביעים בזמן O(n), אבל כללי הזזת המצביעים ומה שמסכמים שונים.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def maxArea(height):
# כתבו כאן קודמקרה 1
מקרה 2
קלט
height = [3, 7, 2, 5, 4, 7, 3, 6]
צפוי
36