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.
- קלט
- height = [4, 4]
- פלט
- 4
- הסבר
- שתי שורות יוצרות מכל אחד בדיוק: גובה 4 ורוחב 1, כך שהוא מכיל 4.
שאלת המשך
כאן מתעלמים מהקווים שבין שני הקווים שלך. אם כל קו היה עמוד מוצק, כמה מים היו נאספים ביניהם? אפשר לחשב את זה גם ב־O(n)?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
התחל בשני הקווים החיצוניים: הם יוצרים את המכל הרחב ביותר. הזזת אחד הקצוות פנימה עולה יחידת רוחב אחת. איזה משני הקווים עשוי לפצות על כך?
המים מוגבלים על ידי הקו הקצר יותר. הזזת הקו הגבוה יותר פנימה משאירה את הגבול הזה ומפחיתה את הרוחב, ולכן היא לעולם לא יכולה לעזור. רק החלפת הקו הקצר יותר עשויה לעזור.
השאר מצביע בכל קצה. מדוד את המים שביניהם ושמור את הערך הטוב ביותר, ואז הזז את המצביע שבקו הקצר יותר צעד אחד פנימה. עצור כשהמצביעים נפגשים.
פתרון
בדיקת כל n²/2 הזוגות פירושה 5 × 10^7 מכפלות עבור 10^4 קווים. כמות המים תלויה רק בקו הקצר יותר בזוג, ולכן ברגע שקו הוא הצד הקצר יותר של המכל הרחב ביותר שהוא עדיין יכול ליצור, אף מכל צר יותר שמשתמש בו לא יוכל להניב תוצאה טובה יותר. שני מצביעים הופכים את זה למעבר יחיד משני הקצוות.
בדוק כל זוג
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
זוג i < j מכיל min(height[i], height[j]) × (j - i): המים נשפכים מעל הדופן הקצרה יותר, ורוחב הקרקעית הוא j - i. נסה את כל הזוגות ושמור את הגדול ביותר.
n קווים נותנים n(n-1)/2 זוגות: בערך 5 × 10^7 עבור 10^4 קווים, ומספר הזוגות גדל פי ארבעה בכל פעם ש-n מוכפל.
אלגוריתם
- הגדר את
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 הוא הצלע הקצרה יותר של מכל, בן הזוג שלו יכול להיות כל קו שגובהו לפחות כגובהו. לכן המכל הטוב ביותר מהסוג הזה משדך אותו לקו הרחוק ביותר שגובהו לפחות כגובהו.
מקמו את הקווים מהגבוה ביותר לנמוך ביותר. כשמגיע תורו של קו i, כל קו שכבר מוקם גבוה לפחות כמוהו, והקו הרחוק ביותר הוא האינדקס השמאלי או הימני ביותר מבין האינדקסים שכבר מוקמו, lo או hi. לכן קו i יכול להכיל לכל היותר height[i] × max(i - lo, hi - i), והמכל הטוב ביותר נספר כשמגיע תורו של הקו הקצר יותר שלו. מבין שני קווים שווים בגובהם, השני שמוקם רואה בראשון בן זוג.
בדוגמה הראשונה, קווי ה־7 במיקומים 1 ו־5 מגיעים ראשונים ומכילים 28. לאחר מכן, קו ה־6 במיקום 7 רואה את lo = 1 ומכיל 36. המיון דורש זמן O(n log 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 מצמיד לו קו קרוב יותר, ולכן הוא צר יותר וגובהו אינו עולה על height[left]. אף אחד מהם לא מכיל יותר מים מאלה שמדדת, ולכן סיימנו עם הקו left, ו-left זז צעד אחד ימינה. בגבהים שווים שני הקווים סיימו את תפקידם, ולכן אפשר להזיז כל אחד מהם.
בכל צעד יוצא קו אחד מהמשחק, ולכן המצביעים נפגשים אחרי n-1 צעדים. לעולם לא מדלגים על הזוג הטוב ביותר: כשמסירים את הראשון מבין שני הקווים שלו, המיכל שנמדד באותו רגע מכיל לפחות אותה כמות מים.
בדוגמה הראשונה, במיקומים 0 ו-7 יש 21, וה-3 מוסר. במיקומים 1 ו-7 יש 36, וה-6 מוסר. בשאר המקרים הכמויות הן 15, 28, 12, 10 ו-2.
אלגוריתם
- הגדר את
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.
- שימוש בקו הגבוה יותר, או בממוצע של השניים, בתור הגובה. המים נשפכים מעל הדופן הנמוכה יותר, ולכן הגובה הוא המינימום.
- מדידת הרוחב בתור
j - i + 1. הקווים שבמיקומיםiו־jנמצאים במרחקj - iזה מזה, ולכן[4, 4]מכיל 4, לא 8. - הנחה שהתשובה משתמשת בקווים הגבוהים ביותר או בזוג החיצוני. בדוגמה הראשונה, שני ערכי ה־7 מכילים 28 והזוג החיצוני 21, בעוד שהתשובה היא 36.
שאלות נפוצות3
מהי סיבוכיות הזמן של Container With Most Water?
פתרון שני המצביעים רץ בזמן O(n) ומשתמש בזיכרון נוסף של O(1), מכיוון שבכל צעד אחד המצביעים זז פנימה במיקום אחד. בדיקת כל זוג אורכת O(n²), ומיון הקווים לפי גובה אורכים O(n log n).
למה להזיז את המצביע אל הקו הקצר יותר?
גובה המים מוגבל על ידי הקו הקצר יותר. לכל מיכל אחר ששומר על אותו קו יש קו נוסף קרוב יותר פנימה, ולכן הוא צר יותר ולא גבוה יותר. אף אחד מהם לא יכול להיות טוב יותר מהמיכל שמדדת, ולכן אפשר לוותר על הקו הקצר יותר בלי לאבד את התשובה.
האם בעיית המכל שמכיל הכי הרבה מים היא בעיה חמדנית?
כן. בכל צעד מתקבלת בחירה מקומית שלעולם לא מבטלים: זורקים את הקו הקצר יותר. הבחירה בטוחה כי כל מְכָל שהיא פוסלת אינו טוב יותר ממְכָל שכבר נמדד, ולכן הבעיה מסווגת גם כחמדנית וגם כשני מצביעים.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def maxArea(height):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
ארגומנט
height = [3, 7, 2, 5, 4, 7, 3, 6]
הפלט הצפוי
36