והפעם נדבר על שאלת 42. LeetCode - Trapping Rain Water הבאה:
נותנים לנו רשימת מספרים, שמייצגים גובה של עמודים שעומדים אחד ליד השני. כאשר גובה של עמוד, יכול להיות מ 0 ומעלה. כאשר 0 פירושו שיש שם שטח ריק בלי עמוד כלשהו.
ואנחנו צריכים לחשב, כמה מים יהיו כלואים, בין העמודים האלו בהתאם לחוק כלים שלובים.
לדוגמה נתונים עמודים בהתאם לגבהים הבאים [0,1,0,2,1,0,1,3,2,1,2,1] שנראים כך:
![]()
אם ננסה לדמיין מים שנשפכים מעל העמודים האלו, נראה שלצורך העניין יש כמות של 6 קוביות מים כלואות, ע"פ ההסבר הבא:
בין העמוד השני [שבגובה 1] לבין העמוד הרביעי [שבגובה 2], תהיה כלואה קוביית מים 1.
בין העמוד הרביעי [שבגובה 2] לבין העמוד השמיני [שבגובה 3] יהיו כלואות 4 קוביות מים.
ובין העמוד התשיעי [שבגובה 2] לבין העמוד ה11 [שבגובה 2] תהיה כלואה קוביית מים 1.
דהיינו, סה"כ 6 קוביות מים.
![]()
אז איך ניגשים לפתור את השאלה הזאת? בהינתן לנו רשימת גבהים של עמודים, איך נוכל לדעת כמה מים יכנסו בין העמודים האלו? איך ניגשים לזה?
אז בתור התחלה ננסה לחלק את השאלה לחלקים. אז מה בעצם שואלים אותנו?
נותנים לנו רשימת מספרים. כל מספר מייצג גובה של עמוד. אנחנו אמורים לחשב את הכמות הכללית של כל המים שיכולים להיות כלואים בין העמודים.
אז בעצם כדי לפתור את השאלה הזאת, לשם כך יש לנו לבצע כמה שלבים. שלב 1 יהיה לחשב האם וכמה מים נכנסים במקום של כל עמוד (דהיינו מעל כל עמוד). השלב ה 2 יהיה לסכום את כל המים שנכנסים בכל המקומות של העמודים. או במילים אחרות, קודם כל נצטרך לחשב כמה מים נכנסים במקום של כל עמוד בפני עצמו ורק אחר כך נוכל לחשב את סך כל המים שנכנסים בכל העמודים.
ולכן בתור התחלה, במקום שנשאל את עצמנו, כמה מים נכנסים בתוך כל העמודים, נשאל את עצמנו, איך אנחנו יכולים לדעת כמה מים נכנסים במקום של כל עמוד בפני עצמו. דהיינו, ננסה להתמקד בלהבין את הנוסחה, איך לדעת כמה מים נכנסים מעל כל עמוד בודד.
ואיך אפשרי לדעת כמה מים נכנסים במקום של כל אחד מהעמודים בפני עצמו?
אז גם את השאלה הזאת נחלק אותה לחלקים. ומי שיתבונן יראה, כי כמות המים שנכנסת מעל כל עמוד, תלויה ב 2 גורמים, שהם: 1 - גובה מפלס המים האפשרי במיקום של העמוד. 2 - גובה העמוד עצמו.
שאז אם ניקח את גובה מפלס המים האפשרי באותו מיקום ונפחית ממנו את גובה העמוד שבאותו מיקום, אז נוכל לקבל את כמות המים הכלואים מעל העמוד.
לדוגמה בדוגמה לעיל, עמוד מספר 7, הגובה שלו הוא 1, גובה מפלס המים האפשרי באותו מיקום הוא 2 (בגלל העמוד במיקום 8 ובמיקום 4). ולכן כמות המים הכלואים מעל העמוד, היא 1.
או במילים אחרות, אנחנו בעצם מבינים, כי כדי לדעת כמה מים כלואים במיקום של העמוד, לשם כך קודם כל צריכים לדעת את גובה מפלס המים האפשרי במיקום של העמוד. ורק אחר כך להפחית ממנו את גובה העמוד הנוכחי וככה לדעת את כמות המים. ורק אחר כך לסכום את כל הכמויות כדי לדעת את הכמות הכללית.
ולכן בשלב הראשון נצטרך לחשב את גובה מפלס המים האפשרי בכל נקודה מעל כל עמוד.
דהיינו, במקום לנסות לחשוב, כמה מים כלואים יש בכל נקודה, ננסה לחשוב, מה גובה המים המקסימאלי האפשרי בכל נקודה.
ואיך ניגשים לזה? איך יודעים מה גובה מפלס המים האפשרי מעל כל עמוד?
אז כדי לדעת מה גובה מפלס המים המקסימאלי האפשרי מעל כל עמוד, לשם כך נצטרך לדעת את החוקיות של מפלס המים. איך היא עובדת? במה תלוי גובה מפלס המים האפשרי בכל נקודה?
אז כמובן שיש לנו את חוק כלים שלובים, שאומר שפני המים תמיד יהיו באותו הגובה. בנוסף יש לנו כמובן גם את האילוץ של הגובה של העמודים, שאמורים להחזיק את המים. ובכך בעצם תלוי גובה פני המים האפשרי בכל נקודה.
דהיינו, גובה מפלס המים האפשרי, תלוי בגובה העמודים שתוחמים ושכולאים בתוכם את המים ובחוק כלים שלובים, שאומר שתמיד המים יהיו באותו הגובה.
אבל איך נוכל לחשב את גובה פני המים האפשרי? מהי הנוסחה לכך?
אז איך יודעים מהי הנוסחה לחשב את גובה פני המים האפשרי בכל נקודה?
לשם כך ננסה שוב לחלק לחלקים ולחפש את המקרה הפשוט ביותר וכך ננסה להבין את החוקיות. אז מהו המקרה הפשוט ביותר?
המקרה הפשוט ביותר הוא כאשר אין שום עמודים כלשהם.
[0,0,0,0,0,0]
כמה מים כלואים יהיו במקרה כזה? תשובה: 0.
ועכשיו נלך למקרה קצת יותר מורכב. מה יהיה במקרה של עמוד 1 בגובה של 1?
[0,0,1,0,0,0]
כמה מים יכול העמוד הזה להחזיק? תשובה: 0. כי עמוד 1 לא יכול לאגור בתוכו מים.
ואיך נדע אם זה נכון? אולי אנחנו מפספסים משהו? אולי זה שהעמוד לא אוגר מים זה בגלל הגובה שלו? תשובה: ננסה לבדוק מקרה שיש עמוד 1 בגובה של 100 או של 1000.
[0,0,100,0,0,0] [0,0,1000,0,0,0]
מה יקרה במקרה כזה? כמה מים ייאגרו? תשובה: 0. או במילים אחרות, אנחנו יודעים בוודאות, שכל עמוד בודד בכל גובה, לא יאגור בתוכו מים. שזה גם נשמע הגיוני. כי כדי לאגור מים צריך 2 עמודים שיחזיקו ביניהם את המים.
עכשיו כדי לנסות להבין את החוקיות של גובה האפשרי של מפלס המים, נלך למקרה קצת יותר מורכב, שבו יש לנו 2 עמודים צמודים אחד לשני באותו הגובה. לדוגמה 2 עמודים בגובה 100.
[0,0,100,100,0,0]
מה יקרה במקרה כזה? כמה מים הם יאגרו ביניהם? תשובה: 0. שני עמודים צמודים, לא יאגרו בתוכם מים.
ומה יקרה אם 2 העמודים יהיו בגובה שונה, אבל עדיין צמודים, לדוגמה עמוד בגובה 100 ליד עמוד בגובה 50.
[0,0,100,50,0,0]
מה יקרה? תשובה: עדיין 2 העמודים לא יאגרו בתוכם מים. במילים אחרות. אנחנו בטוחים, ש 0 עמודים או עמוד 1 או 2 עמודים צמודים אחד לשני, לא משנה מה הגבהים שלהם, הם לא אוגרים מים.
עכשיו ננסה לראות מה יקרה במקרה קצת יותר מורכב, שמייצג 2 עמודים בגובה 100 שביניהם יש מקום בלי שום עמוד.
[0,100,0,100,0]
כמה מים יאגרו במקרה הזה? התשובה תהיה 100. כי במקום שאין עמוד, מפלס המים יהיה 100.
ומה יקרה במקרה שמייצג 2 עמודים בגובה 50 שביניהם יש מקום 1 בלי שום עמוד.
[0,50,0,50,0]
כמה מים יאגרו במקרה הזה? התשובה תהיה 50. כי במקום שאין עמוד, מפלס המים יהיה 50.
אז מהי החוקיות שגילינו עד עכשיו?
חוקיות 1 היא, שהגובה של מפלס המים תלוי בגובה של העמודים.
חוקיות 2 היא, שהמים שנאגרים, ייאגרו רק בין עמודים בלבד.
אבל כמובן שאנחנו צריכים לנסות להבין חוקיות יותר מדוייקת. ולכן ננסה להתקדם למקרה יותר מורכב.
מה לדוגמה יקרה במקרה שמייצג 2 עמודים, עמוד ראשון בגובה של 100 ועמוד שני בגובה של 50, שיש ביניהם מקום 1 ריק בלי עמודים.
[0,100,0,50,0]
כמה מים ייאגרו במקרה הזה? התשובה תהיה 50. כי גובה המפלס של המים, מוגבל לגובה של העמוד / הדופן הנמוכה ביותר שמחזיקה את המים.
ומה לדוגמה יקרה במקרה שמייצג 2 עמודים, עמוד ראשון בגובה של 100 ועמוד שני בגובה של 200, שיש ביניהם מקום 1 ריק בלי עמודים.
[0,100,0,200,0]
כמה מים ייאגרו במקרה הזה? התשובה תהיה 100. כי כנ"ל גובה המפלס של המים, מוגבל לגובה של העמוד / הדופן הנמוכה ביותר שמחזיקה את המים.
דהיינו, אנחנו מבינים, שהגובה של מפלס המים לעולם לא יהיה יותר גבוה מהגובה של הדופן הנמוכה ביותר שמחזיקה את המים. אלא הגובה של מפלס המים, תמיד יהיה זהה לגובה של הדופן הנמוכה ביותר.
ועכשיו ננסה לקחת מקרה קצת יותר מסובך וננסה להבין אותו. מה יקרה לצורך העניין במקרה הזה, שיש בו: עמוד של 25, מקום ריק, עמוד של 100, מקום ריק, עמוד של 50.
[0,25,0,100,0,50,0]
מה יקרה במקרה הזה? התשובה היא, שבין העמוד של ה 100 לבין העמוד של ה 25, גובה המים יהיה 25. ובין העמוד של ה 100 לבין העמוד של ה 50, הגובה יהיה 50. כי שוב כנ"ל הגובה של המים יהיה בהתאם לגובה של העמוד הנמוך ביותר שתוחם את המים.
אבל האם זאת כל האמת? האם יהיה נכון לומר, שהגובה האפשרי של המים, תמיד יהיה בהתאם לגובה של העמוד הנמוך ביותר שתוחם אותו? אז נבדוק את המקרה הבא, שיש בו: עמוד של 100, מקום ריק, עמוד של 25, מקום ריק, עמוד של 50.
[0,100,0,25,0,50,0]
מה יקרה במקרה הזה? התשובה היא, שגובה מפלס המים (לא כמות המים אלא מפלס המים), בין ה 100 לבין העמוד של ה 25 יהיה 50. דהיינו, גובה מפלס המים שתחומים בין ה 25 לבין ה 100 יהיה 50 ולא יהיה בהתאם לגובה של הדופן שתוחמת את המים.
אז האם יהיה נכון לומר, שתמיד גובה מפלס המים יהיה בהתאם לגובה של העמוד הנמוך ביותר שתוחם ומגביל את המים? תשובה: לא. כי במקרה הזה לדוגמה, הגובה יהיה 50 כנ"ל.
וגם בין העמוד 50 לבין העמוד 25, גם שם גובה המים יהיה 50. כי העמוד של ה 100 מאגף מצד שמאל, את העמוד של ה 25 ולכן יכולים להיות בין העמוד של ה 50 לבין של ה 25, יותר מים מאשר הגובה של ה 25.
אז מה בעצם הבנו עד כאן, לגבי החוקיות של גובה מפלס המים המקסימאלי האפשרי בכל נקודה?
הבנו שחוק 1 - בכל נקודה, את המים תמיד יתחום העמוד הגבוה ביותר מצד ימין של אותו המקום + העמוד הגבוה ביותר מצד שמאל של אותו המקום.
חוק 2 - גובה מפלס המים בכל נקודה, תמיד יהיה מוגבל לגובה של העמוד הנמוך ביותר שתוחם את המים באותה הנקודה.
לדוגמה במקרה הנ"ל של [0,100,0,25,0,50,0]
בנקודה של העמוד שבגובה של 25, מפלס המים יהיה 50. כי העמוד הגבוה ביותר מצד ימין, הוא 50 והעמוד הגבוה ביותר מצד שמאל, הוא 100. ולכן המים נתחמים על ידי העמודים של ה 50 מצד ימין ושל ה 100 מצד שמאל.
ובין 2 העמודים הגבוהים ביותר שנמצאים מצדדי הנקודה הנוכחית, מביניהם נצטרך למצוא את העמוד הנמוך ביותר. שהוא הגבול האפשרי של מפלס המים.
שזה בעצם אומר, שאנחנו מצד אחד צריכים למצוא את הנקודה הגבוהה ביותר שתתחום את המים ומצד שני אנחנו צריכים למצוא את הנקודה הנמוכה ביותר, מבין 2 הנקודות הגבוהות ביותר.
שזה בעצם אומר, שבכל נקודה אנחנו נרצה לדעת, מהו העמוד הכי גבוה מצד ימין של אותו המקום וגם מהו העמוד הכי גבוה מצד שמאל של אותו המקום. ואז הגובה הנמוך ביותר, מבין 2 העמודים הגבוהים ביותר, הוא יהיה הגובה המקסימאלי האפשרי של מפלס המים.
אבל איך נוכל לדעת בכל נקודה, מהו העמוד הכי גבוה מצד ימין ומהו העמוד הכי גבוה מצד שמאל, כדי שנוכל לדעת את הגובה המקסימאלי האפשרי של מפלס המים?
תשובה: נעצור כאן לרגע בתהליך וננסה לחשוב על הדברים בצורה אחרת יותר פשוטה. ננסה להבין טוב יותר את המשימה של לחפש בכל נקודה, את העמוד הגבוה ביותר מצד ימין ואת העמוד הגבוה ביותר מצד שמאל.
אז מה בעצם אנחנו מבינים עד כה, אנחנו מבינים שבכל נקודה נצטרך לחשב כמה חישובים, שהם:
1 - מהו העמוד הגבוה ביותר שמצד ימין ביחס לאותה הנקודה הנוכחית?
2 - מהו העמוד הגבוה ביותר שמצד שמאל ביחס לאותה הנקודה הנוכחית?
3 - מבין 2 העמודים האלו, מהו העמוד הנמוך ביותר מביניהם?
ו 3 השאלות האלו, יתנו לנו את מפלס המים האפשרי בנקודה הנוכחית.
אבל האם זאת כל האמת? האם באמת אנחנו תמיד צריכים לעשות את 3 החישובים האלו, כדי לדעת מהו מפלס המים האפשרי בכל נקודה?
ולכאורה התשובה היא שכן. כי אנחנו צריכים לדעת מה הגובה הגבוה ביותר של העמודים שתוחמים את המים וכולי כנ"ל. אבל זאת לא כל האמת. למה?
אז ננסה לדייק את מה שהבנו עד כה. הבנו כי כדי לדעת מה גובה מפלס המים המקסימאלי האפשרי בנקודה כלשהי, לשם כך עלינו לדעת:
1 - מה גובה העמוד הגבוה ביותר מצד ימין של אותה הנקודה הנוכחית
2- מה גובה העמוד הגבוה ביותר מצד שמאל של אותה הנקודה הנוכחית
3 - מה גובה העמוד הנמוך ביותר מבין 2 העמודים הנ"ל
וזה בעצם נותן לנו את גובה מפלס המים המקסימאלי האפשרי בנקודה כלשהי
כאשר, אם נפחית את גובה העמוד עצמו, אז נקבל את כמות המים הכלואים באותה הנקודה.
ונשאל את השאלה הבאה:
האם יהיה נכון לומר, שאם נדע בכל מיקום, את הנקודה הגבוה ביותר מצד ימין ואת הנקודה הגבוה ביותר מצד שמאל, אז נוכל לדעת את גובה מפלס המים כנ"ל? תשובה: כן. הטענה הנ"ל היא אמת.
אבל האם מכך ניתן להסיק שבהכרח צריך לדעת בכל נקודה את גובה 2 הנקודות הגבוהות ביותר שתוחמות את אותה הנקודה? תשובה: לא.
ואני אסביר. למה אנחנו מחפשים את הנקודה הגבוה ביותר, מ 2 הצדדים של הנקודה הנוכחית? למה שלא נסתפק ב 2 נקודות גובה כלשהן, לצידי המיקום הנוכחי שלנו? תשובה: כי אולי מפלס המים יכול להיות גבוה יותר, מאשר 2 הנקודות האקראיות שנמצאות לצד הנקודה הנוכחית שלנו.
לדוגמה במקרה של: [5,4,3,2,1,2,3,4,5] גובה מפלס המים היכן שנמצא העמוד האמצעי, שהוא העמוד בגובה 1, יהיה 5 והוא לא יהיה רק לפי הגובה של העמודים שצמודים אליו. אלא אנחנו חייבים למצוא את 2 הנקודות הגבוהות ביותר משני הצדדים של המיקום הנוכחי שלנו. אבל האם זאת באמת כל האמת?
והתשובה היא, שלא! ולמה, כי בסופו של דבר, מפלס המים מוגבל לגובה של העמוד הנמוך ביותר מבין 2 העמודים ההכי גבוהים שנמצאים לצידי המיקום הנוכחי שלנו.
ומאחר שאנחנו מוגבלים לגובה הנמוך ביותר, של אחד הגבהים הגבוהים ביותר, זה בעצם אומר, שבמקרה כזה לדוגמה
[5,4,3,2,1,200,300,400,500]
אם נדע שמצד שמאל של העמוד האמצעי, העמוד בגובה 1, אם נדע שמצד שמאל שלו, העמוד הגבוה ביותר הוא 5, האם זה ישנה לנו מהו גובה העמוד הגבוה ביותר שלו, מצד ימין. האם זה משנה לנו אם העמוד בגובה של 1, תחום ב 5+200 או ב 5+300 או ב 5+כל מספר אחר שגבוה מהמספר 5?
התשובה היא שלא. כי בכל מקרה מפלס המים לא יהיה גבוה יותר מ 5.
וזה בעצם אומר, שאם אנחנו יודעים מה הגובה הגבוה ביותר מצד 1 כלשהו של המיקום הנוכחי, הרי שאנחנו כבר לא צריכים לדעת מה הגובה של העמוד הגבוה ביותר מהצד שני. אלא אנחנו צריכים לעשות את החישוב הבא:
ניקח לדוגמה את המקרה הבא:
[3,1,0,7,1,3,1,5,0,9,2,5,1,4,0,0,10,1,4,6]
![]()
נסתכל לצורך העניין על העמוד השני, שהגובה שלו הוא 1. נבדוק מה הגובה של העמוד הגבוה ביותר שנמצא מצד שמאל שלו. ונראה שזה העמוד הראשון שהוא בגובה של 3.
וזה בעצם אומר, שאנחנו יודעים בוודאות, שמצד שמאל של העמוד השני שלנו, יש עמוד בגובה של 3. דהיינו, אנחנו יודעים בוודאות שלא משנה מה, מפלס המים לא יהיה יותר גבוה מ 3.
אבל האם אנחנו יכולים לדעת בוודאות שמפלס המים במיקום של העמוד השני, יהיה 3? אולי הוא יהיה 2 או 1 או אולי אפילו 0? איך נדע את זה?
אז במה זה תלוי? לשם כך נצטרך לבדוק את הגובה של העמודים שנמצאים בצד הימני של המיקום השני. ואז יש לנו כמה אפשרויות.
1 - אם כל העמודים שנמצאים מהצד הימני, הם נמוכים מ 3, דהיינו, אם העמוד הגבוה ביותר מצד ימין, הוא קטן מ 3, הרי שמפלס המים לא יהיה 3, אלא הוא יהיה מוגבל לגובה של העמוד הגבוה ביותר שנמצא מצד ימין של העמוד השני.
2 - אם מצד ימין של העמוד השני, יש עמוד כלשהו, שהגובה שלו הוא 3 או יותר, דהיינו, שהגובה שלו הוא זהה או גדול מהגובה של העמוד הגבוה ביותר השמאלי ביותר, הרי שאנחנו יכולים לדעת בוודאות שגובה מפלס המים יהיה 3 ולא יותר. לא משנה מה. כי בסוף, המים מוגבלים לגובה של העמוד הנמוך ביותר מבין 2 העמודים הגבוהים ביותר.
דהיינו, במקרה שלנו, אם נסתכל לצד ימין של המיקום השני, הרי שנוכל לראות עמודים גבוהים יותר מ 3. וזה בעצם אומר, שמפלס המים במיקום 2, יהיה לא יותר גבוה מ 3. ואנחנו יודעים את זה בוודאות, גם בלי לדעת מה הגובה הגבוה ביותר מצד ימין, של העמוד שנמצא במיקום השני.
או במילים אחרות, כאשר אנחנו מוצאים את הגובה של העמוד הגבוה ביותר, מצד 1 כלשהו, צד ימין או שמאל, של מיקום כלשהו, הרי שאנחנו לא צריכים למצוא את הגובה של העמוד הגבוה ביותר מהצד שני, אלא אנחנו צריכים לוודא שמהצד השני יש עמוד בגובה זהה או גבוה יותר, מהגובה של העמוד הגבוה ביותר, מהצד שכבר מצאנו.
לדוגמה, אם נגלה שהעמוד הגבוה ביותר מצד ימין הוא 100, אז נצטרך לוודא שמצד שמאל יש עמוד בגובה של 100 או יותר. וזהו. אבל אח"כ לא נצטרך להמשיך לחפש את הגובה של העמוד הגבוה ביותר מצד שמאל. אלא אם לא נמצא עמוד בגובה זהה או גבוה מהעמוד שמצאנו בצד ימין, שאז נצטרך להמשיך לחפש את העמוד הגבוה ביותר גם בצד השני.
אז בהתאם להבנה הזאת, ננסה להסתכל על המקרה הקודם:
[3,1,0,7,1,3,1,5,0,9,2,5,1,4,0,0,10,1,4,6]
![]()
נסתכל לצורך העניין על העמוד השני, שהגובה שלו הוא 1. נבדוק מה הגובה של העמוד הגבוה ביותר שנמצא מצד שמאל שלו. ונראה שזה העמוד הראשון שהוא בגובה של 3.
וזה בעצם אומר, שאנחנו יודעים בוודאות, שמצד שמאל של העמוד השני שלנו, יש עמוד בגובה של 3. דהיינו, אנחנו יודעים בוודאות שלא משנה מה, מפלס המים לא יהיה יותר גבוה מ 3.
אבל האם אנחנו יכולים לדעת בוודאות שמפלס המים במיקום של העמוד השני, יהיה 3? אולי הוא יהיה 2 או 1 או אולי אפילו 0? איך נדע את זה?
אז במה זה תלוי? לשם כך נצטרך לבדוק את הגובה של העמודים שנמצאים בצד הימני של המיקום השני. ואז יש לנו כמה אפשרויות.
1 - אם כל העמודים שנמצאים מהצד הימני, הם נמוכים מ 3, דהיינו, אם העמוד הגבוה ביותר מצד ימין, הוא קטן מ 3, הרי שמפלס המים לא יהיה 3, אלא הוא יהיה מוגבל לגובה של העמוד הגבוה ביותר שנמצא מצד ימין של העמוד השני.
2 - אם מצד ימין של העמוד השני, יש עמוד כלשהו, שהגובה שלו הוא 3 או יותר, דהיינו, שהגובה שלו הוא זהה או גדול מהגובה של העמוד הגבוה ביותר השמאלי ביותר, הרי שאנחנו יכולים לדעת בוודאות שגובה מפלס המים יהיה 3 ולא יותר. לא משנה מה. כי בסוף, המים מוגבלים לגובה של העמוד הנמוך ביותר מבין 2 העמודים הגבוהים ביותר.
דהיינו, במקרה שלנו, אם נסתכל לצד ימין של המיקום השני, הרי שנוכל לראות עמודים גבוהים יותר מ 3. וזה בעצם אומר, שמפלס המים במיקום 2, יהיה לא יותר גבוה מ 3. ואנחנו יודעים את זה בוודאות, גם בלי לדעת מה הגובה הגבוה ביותר מצד ימין, של העמוד שנמצא במיקום השני.
או במילים אחרות, כאשר אנחנו מוצאים את הגובה של העמוד הגבוה ביותר, מצד 1 כלשהו, צד ימין או שמאל, של מיקום כלשהו, הרי שאנחנו לא צריכים למצוא את הגובה של העמוד הגבוה ביותר מהצד שני, אלא אנחנו צריכים לוודא שמהצד השני יש עמוד בגובה זהה או גבוה יותר, מהגובה של העמוד הגבוה ביותר, מהצד שכבר מצאנו.
לדוגמה, אם נגלה שהעמוד הגבוה ביותר מצד ימין הוא 100, אז נצטרך לוודא שמצד שמאל יש עמוד בגובה של 100 או יותר. וזהו. אבל אח"כ לא נצטרך להמשיך לחפש את הגובה של העמוד הגבוה ביותר מצד שמאל. אלא אם לא נמצא עמוד בגובה זהה או גבוה מהעמוד שמצאנו בצד ימין, שאז נצטרך להמשיך לחפש את העמוד הגבוה ביותר גם בצד השני.
אז בהתאם להבנה הזאת, ננסה להסתכל על המקרה הקודם:
[3,1,0,7,1,3,1,5,0,9,2,5,1,4,0,0,10,1,4,6]
![]()
ונסתכל על העמוד הימני ביותר, העמוד במיקום 20 שהגובה שלו הוא 6. וננסה להבין מה אנחנו יכולים להסיק מכך? האם יש משהו שאנחנו יכולים להסיק מכך בוודאות?
אז התשובה היא, שאולי כן. כי בעצם אנחנו יודעים שבמיקום 20, העמוד הגבוה ביותר הוא בגובה של 6. דהיינו, אנחנו כבר יכולים לדעת בוודאות, שלא משנה מה, גובה המים במיקום 20, לא יהיה גבוה יותר מ 6. כי זה העמוד הגבוה ביותר שנמצא בצד ימין. אבל האם גובה המים יהיה 6 או פחות מ 6, איך נדע?
זה כמובן תלוי בגובה של העמודים שנמצאים מצד שמאל של העמוד הימני ביותר.
ואני אדייק, שבפועל בוודאות שלא יהיו מים כלואים, לא במיקום הראשון ולא במיקום האחרון, בכל תרחיש. כי המים הכלואים, חייבים להיות בין 2 עמודים כלשהם. אבל כרגע לצורך הניתוח, אני מתעלם מזה כרגע ומתייחס לכל מיקום, כולל הראשון והאחרון, כאילו הם מיקומים רגילים.
אז בעצם מכך שאנחנו יודעים שבצד ימין, במיקום 20, הגובה הגבוה ביותר הוא 6, הרי שאנחנו יודעים בוודאות שלא יהיו שם מים יותר מגובה של 6. אבל אולי יהיו שם פחות מים בגובה יותר נמוך? אז הרי שכבר יש לנו וודאות חלקית כלשהי. אבל עדיין אין אפשרות להתקדם איתה למסקנה וודאית כלשהי.
אז נסתכל על הנקודה הראשונה מצד שמאל, העמוד הראשון, שהוא בגובה של 3. האם מכך אנחנו יכולים להסיק משהו בוודאות? התשובה היא, שכן!
כי אנחנו יודעים שהעמוד הגבוה ביותר מצד שמאל, דהיינו, העמוד הראשון הוא בגובה 3. ולכן אנחנו יודעים בוודאות שגובה המים לא יהיה יותר גבוה מ 3. אבל האם הוא יהיה אולי פחות מ 3? התשובה היא שלא. הוא יהיה בדיוק 3.
ולמה? כי אנחנו יודעים גם שמצד ימין של המיקום הראשון, יש עמוד בגובה של 6, שהוא העמוד הימני ביותר כנ"ל.
או במילים אחרות, מכך שאנחנו יודעים שהעמוד השמאלי ביותר, הוא 3 והעמוד הימני ביותר הוא 6, הרי שאנחנו יודעים בוודאות, שבמיקום השמאלי הראשון הגובה יהיה בדיוק 3. ולגבי העמוד הימני, אנחנו לא יודעים עדיין מה יהיה הגובה המדוייק. כי הוא אומנם לא יהיה יותר מ 6, אבל אולי הוא יהיה 5 או אולי 4. למרות שאנחנו כבר יודעים שבוודאות הוא יהיה לפחות 3.
דהיינו, לגבי מיקום 1 השמאלי ביותר, אנחנו יודעים שגובה המים בוודאות הוא 3.
לגבי המיקום 20 הימני ביותר, אנחנו יודעים שגובה המים יהיה בין 3 לבין 6. לא פחות מ 3 ולא יותר מ 6.
וכך הגענו לפתרון הבא:
![]()
ובלי קשר אנחנו יודעים, שלא משנה מה, במיקום הימני והשמאלי ביותר, תמיד כמות המים הכלואים, תהיה 0, בכל תרחיש. כי אין 2 עמודים שתוחמים את המיקום הקיצוני ביותר כנ"ל.
ולכן נסמן
![]()
וזה בעצם אומר, שיש לנו וודאות לגבי המיקום הראשון מצד שמאל, בלי לרוץ אפילו פעם אחת על כל הרשימה, אלא מספיק לדעת מה הערך של העמוד הימני ביותר ושל השמאלי ביותר, כדי לפתור בוודאות את הקצה השמאלי ביותר או הימני ביותר, כנ"ל.
אז בעצם הנקודה הוודאית ביותר כרגע, היא מיקום מספר 1, שבו אנחנו יודעים בוודאות את גובה מפלס המים ואת כמות המים הכלואים.
אז עכשיו נעבור לנקודה הקרובה ביותר, לנקודה במיקום מספר 2, שהגובה שם הוא 1. ונשאל, האם יש משהו שאנחנו יכולים לדעת שם בוודאות?
והתשובה היא, שכן! כי בוודאות שבמיקום השמאלי של המיקום השני, דהיינו, במיקום הראשון, בוודאות שגובה מפלס המים הוא 3. ובמיקום השני גובה העמוד הוא 1. דהיינו, גובה העמוד הוא לא גבוה יותר מגובה מפלס המים שנמצא בצד שמאל. ולכן גם במיקום 2, גובה מפלס המים, יהיה בוודאות 3. וכך הגענו לכאן.
![]()
וכך נמשיך גם למיקום מספר 3 ונקבל את התוצאה הזאת:
![]()
ועכשיו נעבור למיקום מספר 4, שבו העמוד הוא בגובה של 7.
אז אנחנו מבינים שמפלס המים כבר לא חייב להיות 3, כי מצד שמאל יש לנו עמוד יותר גבוה מ 3. אנחנו מבינים גם שמפלס המים יכול להיות 7. אנחנו מבינים גם שמפלס המים לא יכול להיות יותר מ 7. כי 7 זה המספר הגדול ביותר מצד שמאל, ביחס למיקום הרביעי שבו אנחנו נמצאים. אבל האם מפלס המים יהיה 7 אולי פחות?
אז אנחנו יודעים שבצד ימין יש עמוד בגובה של 6. שזה בעצם אומר, שבמיקום 4, מפלס המים יהיה לא יותר מ 7 ולא פחות מ 6. דהיינו, או 6 או 7. אבל אין לנו וודאות לגבי מה יהיה גובה מפלס המים במיקום 4.
אבל אנחנו כן יכולים לדעת בוודאות מה יהיה גובה מפלס המים במיקום 20. כי יש שם עמוד בגובה 6 ומצד שמאל שלו יש עמוד בגובה 7. דהיינו, מפלס המים במיקום 20, יהיה 6.
כך:
![]()
אז כרגע יש לנו וודאות לגבי מיקום 20, ויש לנו וודאות חלקית לגבי מיקום 4. ולכן נמשיך במיקום 19, וננסה לראות האם ומה אפשרי להסיק שם.
ושם גובה המים הוא 4, דהיינו, בוודאות שהמפלס יהיה שם 6. וכמות המים הכלואים תהיה 2 כך:
![]()
ואז נמשיך למיקום מספר 18 ונגיע לזה:
![]()
ועכשיו נעבור למיקום מספר 17, ונראה שיש שם עמוד בגובה של 10. דהיינו, נוכל לדעת בוודאות, שמפלס המים שם לא יהיה יותר מ 10, והוא גם לא יהיה פחות מ 7, שזאת הנקודה הגבוה ביותר שידועה לנו עד כה מצד שמאל. ולכן כרגע אנחנו יכולים לדעת שהמים במיקום 17, יהיו בין 7 לבין 10.
אבל נוצרה לנו וודאות, לגבי מיקום 4. שיש שם עמוד בגובה של 7 ומצד ימין יש במיקום 17 עמוד בגובה 10. ולכן בוודאות נוכל לדעת שבמיקום 4, יש מים בגובה 7. לא יותר ולא פחות.
וכך הגענו לכאן:
![]()
וכך נמשיך הלאה עד שנפתור את כל התרגיל, כך:
![]()
![]()
![]()
![]()
![]()
אז איך בעצם פתרנו את השאלה? קודם כל חילקנו לחלקים, לנסות למצוא איך לדעת מה גובה מפלס המים בכל נקודה, בלי קשר לשאלה כמה מים כלואים שם.
אחר כך ניסינו להבין בדיוק את החוקיות של איך לחשב את גובה מפלס המים, במדויק. וברגע שהבנו את הנוסחה במדויק, מכאן עברנו על המיקום הראשון מצד ימין והראשון מצד שמאל וניסינו להבין, האם יש משהו אפילו הקטן ביותר, שהוא בטוח נכון?!
וראינו, שכן יש משהו שהוא בטוח נכון. ובכל פעם סימנו משהו אחר שהוא בטוח נכון. וכך פתרנו את כל התרגיל, בריצה על הרשימה מ 2 הצדדים בו זמנית, כאשר כל צד נותן וודאות או לגבי עצמו או לגבי הצד השני.
לסיכום: לחלק לחלקים הכי קטנים ולנסות להבין האם ומה בטוח נכון.
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
אז קודם כל נסביר את השאלה.Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
נותנים לנו רשימת מספרים, שמייצגים גובה של עמודים שעומדים אחד ליד השני. כאשר גובה של עמוד, יכול להיות מ 0 ומעלה. כאשר 0 פירושו שיש שם שטח ריק בלי עמוד כלשהו.
ואנחנו צריכים לחשב, כמה מים יהיו כלואים, בין העמודים האלו בהתאם לחוק כלים שלובים.
לדוגמה נתונים עמודים בהתאם לגבהים הבאים [0,1,0,2,1,0,1,3,2,1,2,1] שנראים כך:
אם ננסה לדמיין מים שנשפכים מעל העמודים האלו, נראה שלצורך העניין יש כמות של 6 קוביות מים כלואות, ע"פ ההסבר הבא:
בין העמוד השני [שבגובה 1] לבין העמוד הרביעי [שבגובה 2], תהיה כלואה קוביית מים 1.
בין העמוד הרביעי [שבגובה 2] לבין העמוד השמיני [שבגובה 3] יהיו כלואות 4 קוביות מים.
ובין העמוד התשיעי [שבגובה 2] לבין העמוד ה11 [שבגובה 2] תהיה כלואה קוביית מים 1.
דהיינו, סה"כ 6 קוביות מים.
אז איך ניגשים לפתור את השאלה הזאת? בהינתן לנו רשימת גבהים של עמודים, איך נוכל לדעת כמה מים יכנסו בין העמודים האלו? איך ניגשים לזה?
אז בתור התחלה ננסה לחלק את השאלה לחלקים. אז מה בעצם שואלים אותנו?
נותנים לנו רשימת מספרים. כל מספר מייצג גובה של עמוד. אנחנו אמורים לחשב את הכמות הכללית של כל המים שיכולים להיות כלואים בין העמודים.
אז בעצם כדי לפתור את השאלה הזאת, לשם כך יש לנו לבצע כמה שלבים. שלב 1 יהיה לחשב האם וכמה מים נכנסים במקום של כל עמוד (דהיינו מעל כל עמוד). השלב ה 2 יהיה לסכום את כל המים שנכנסים בכל המקומות של העמודים. או במילים אחרות, קודם כל נצטרך לחשב כמה מים נכנסים במקום של כל עמוד בפני עצמו ורק אחר כך נוכל לחשב את סך כל המים שנכנסים בכל העמודים.
ולכן בתור התחלה, במקום שנשאל את עצמנו, כמה מים נכנסים בתוך כל העמודים, נשאל את עצמנו, איך אנחנו יכולים לדעת כמה מים נכנסים במקום של כל עמוד בפני עצמו. דהיינו, ננסה להתמקד בלהבין את הנוסחה, איך לדעת כמה מים נכנסים מעל כל עמוד בודד.
ואיך אפשרי לדעת כמה מים נכנסים במקום של כל אחד מהעמודים בפני עצמו?
אז גם את השאלה הזאת נחלק אותה לחלקים. ומי שיתבונן יראה, כי כמות המים שנכנסת מעל כל עמוד, תלויה ב 2 גורמים, שהם: 1 - גובה מפלס המים האפשרי במיקום של העמוד. 2 - גובה העמוד עצמו.
שאז אם ניקח את גובה מפלס המים האפשרי באותו מיקום ונפחית ממנו את גובה העמוד שבאותו מיקום, אז נוכל לקבל את כמות המים הכלואים מעל העמוד.
לדוגמה בדוגמה לעיל, עמוד מספר 7, הגובה שלו הוא 1, גובה מפלס המים האפשרי באותו מיקום הוא 2 (בגלל העמוד במיקום 8 ובמיקום 4). ולכן כמות המים הכלואים מעל העמוד, היא 1.
או במילים אחרות, אנחנו בעצם מבינים, כי כדי לדעת כמה מים כלואים במיקום של העמוד, לשם כך קודם כל צריכים לדעת את גובה מפלס המים האפשרי במיקום של העמוד. ורק אחר כך להפחית ממנו את גובה העמוד הנוכחי וככה לדעת את כמות המים. ורק אחר כך לסכום את כל הכמויות כדי לדעת את הכמות הכללית.
ולכן בשלב הראשון נצטרך לחשב את גובה מפלס המים האפשרי בכל נקודה מעל כל עמוד.
דהיינו, במקום לנסות לחשוב, כמה מים כלואים יש בכל נקודה, ננסה לחשוב, מה גובה המים המקסימאלי האפשרי בכל נקודה.
ואיך ניגשים לזה? איך יודעים מה גובה מפלס המים האפשרי מעל כל עמוד?
אז כדי לדעת מה גובה מפלס המים המקסימאלי האפשרי מעל כל עמוד, לשם כך נצטרך לדעת את החוקיות של מפלס המים. איך היא עובדת? במה תלוי גובה מפלס המים האפשרי בכל נקודה?
אז כמובן שיש לנו את חוק כלים שלובים, שאומר שפני המים תמיד יהיו באותו הגובה. בנוסף יש לנו כמובן גם את האילוץ של הגובה של העמודים, שאמורים להחזיק את המים. ובכך בעצם תלוי גובה פני המים האפשרי בכל נקודה.
דהיינו, גובה מפלס המים האפשרי, תלוי בגובה העמודים שתוחמים ושכולאים בתוכם את המים ובחוק כלים שלובים, שאומר שתמיד המים יהיו באותו הגובה.
אבל איך נוכל לחשב את גובה פני המים האפשרי? מהי הנוסחה לכך?
אז איך יודעים מהי הנוסחה לחשב את גובה פני המים האפשרי בכל נקודה?
לשם כך ננסה שוב לחלק לחלקים ולחפש את המקרה הפשוט ביותר וכך ננסה להבין את החוקיות. אז מהו המקרה הפשוט ביותר?
המקרה הפשוט ביותר הוא כאשר אין שום עמודים כלשהם.
[0,0,0,0,0,0]
כמה מים כלואים יהיו במקרה כזה? תשובה: 0.
ועכשיו נלך למקרה קצת יותר מורכב. מה יהיה במקרה של עמוד 1 בגובה של 1?
[0,0,1,0,0,0]
כמה מים יכול העמוד הזה להחזיק? תשובה: 0. כי עמוד 1 לא יכול לאגור בתוכו מים.
ואיך נדע אם זה נכון? אולי אנחנו מפספסים משהו? אולי זה שהעמוד לא אוגר מים זה בגלל הגובה שלו? תשובה: ננסה לבדוק מקרה שיש עמוד 1 בגובה של 100 או של 1000.
[0,0,100,0,0,0] [0,0,1000,0,0,0]
מה יקרה במקרה כזה? כמה מים ייאגרו? תשובה: 0. או במילים אחרות, אנחנו יודעים בוודאות, שכל עמוד בודד בכל גובה, לא יאגור בתוכו מים. שזה גם נשמע הגיוני. כי כדי לאגור מים צריך 2 עמודים שיחזיקו ביניהם את המים.
עכשיו כדי לנסות להבין את החוקיות של גובה האפשרי של מפלס המים, נלך למקרה קצת יותר מורכב, שבו יש לנו 2 עמודים צמודים אחד לשני באותו הגובה. לדוגמה 2 עמודים בגובה 100.
[0,0,100,100,0,0]
מה יקרה במקרה כזה? כמה מים הם יאגרו ביניהם? תשובה: 0. שני עמודים צמודים, לא יאגרו בתוכם מים.
ומה יקרה אם 2 העמודים יהיו בגובה שונה, אבל עדיין צמודים, לדוגמה עמוד בגובה 100 ליד עמוד בגובה 50.
[0,0,100,50,0,0]
מה יקרה? תשובה: עדיין 2 העמודים לא יאגרו בתוכם מים. במילים אחרות. אנחנו בטוחים, ש 0 עמודים או עמוד 1 או 2 עמודים צמודים אחד לשני, לא משנה מה הגבהים שלהם, הם לא אוגרים מים.
עכשיו ננסה לראות מה יקרה במקרה קצת יותר מורכב, שמייצג 2 עמודים בגובה 100 שביניהם יש מקום בלי שום עמוד.
[0,100,0,100,0]
כמה מים יאגרו במקרה הזה? התשובה תהיה 100. כי במקום שאין עמוד, מפלס המים יהיה 100.
ומה יקרה במקרה שמייצג 2 עמודים בגובה 50 שביניהם יש מקום 1 בלי שום עמוד.
[0,50,0,50,0]
כמה מים יאגרו במקרה הזה? התשובה תהיה 50. כי במקום שאין עמוד, מפלס המים יהיה 50.
אז מהי החוקיות שגילינו עד עכשיו?
חוקיות 1 היא, שהגובה של מפלס המים תלוי בגובה של העמודים.
חוקיות 2 היא, שהמים שנאגרים, ייאגרו רק בין עמודים בלבד.
אבל כמובן שאנחנו צריכים לנסות להבין חוקיות יותר מדוייקת. ולכן ננסה להתקדם למקרה יותר מורכב.
מה לדוגמה יקרה במקרה שמייצג 2 עמודים, עמוד ראשון בגובה של 100 ועמוד שני בגובה של 50, שיש ביניהם מקום 1 ריק בלי עמודים.
[0,100,0,50,0]
כמה מים ייאגרו במקרה הזה? התשובה תהיה 50. כי גובה המפלס של המים, מוגבל לגובה של העמוד / הדופן הנמוכה ביותר שמחזיקה את המים.
ומה לדוגמה יקרה במקרה שמייצג 2 עמודים, עמוד ראשון בגובה של 100 ועמוד שני בגובה של 200, שיש ביניהם מקום 1 ריק בלי עמודים.
[0,100,0,200,0]
כמה מים ייאגרו במקרה הזה? התשובה תהיה 100. כי כנ"ל גובה המפלס של המים, מוגבל לגובה של העמוד / הדופן הנמוכה ביותר שמחזיקה את המים.
דהיינו, אנחנו מבינים, שהגובה של מפלס המים לעולם לא יהיה יותר גבוה מהגובה של הדופן הנמוכה ביותר שמחזיקה את המים. אלא הגובה של מפלס המים, תמיד יהיה זהה לגובה של הדופן הנמוכה ביותר.
ועכשיו ננסה לקחת מקרה קצת יותר מסובך וננסה להבין אותו. מה יקרה לצורך העניין במקרה הזה, שיש בו: עמוד של 25, מקום ריק, עמוד של 100, מקום ריק, עמוד של 50.
[0,25,0,100,0,50,0]
מה יקרה במקרה הזה? התשובה היא, שבין העמוד של ה 100 לבין העמוד של ה 25, גובה המים יהיה 25. ובין העמוד של ה 100 לבין העמוד של ה 50, הגובה יהיה 50. כי שוב כנ"ל הגובה של המים יהיה בהתאם לגובה של העמוד הנמוך ביותר שתוחם את המים.
אבל האם זאת כל האמת? האם יהיה נכון לומר, שהגובה האפשרי של המים, תמיד יהיה בהתאם לגובה של העמוד הנמוך ביותר שתוחם אותו? אז נבדוק את המקרה הבא, שיש בו: עמוד של 100, מקום ריק, עמוד של 25, מקום ריק, עמוד של 50.
[0,100,0,25,0,50,0]
מה יקרה במקרה הזה? התשובה היא, שגובה מפלס המים (לא כמות המים אלא מפלס המים), בין ה 100 לבין העמוד של ה 25 יהיה 50. דהיינו, גובה מפלס המים שתחומים בין ה 25 לבין ה 100 יהיה 50 ולא יהיה בהתאם לגובה של הדופן שתוחמת את המים.
אז האם יהיה נכון לומר, שתמיד גובה מפלס המים יהיה בהתאם לגובה של העמוד הנמוך ביותר שתוחם ומגביל את המים? תשובה: לא. כי במקרה הזה לדוגמה, הגובה יהיה 50 כנ"ל.
וגם בין העמוד 50 לבין העמוד 25, גם שם גובה המים יהיה 50. כי העמוד של ה 100 מאגף מצד שמאל, את העמוד של ה 25 ולכן יכולים להיות בין העמוד של ה 50 לבין של ה 25, יותר מים מאשר הגובה של ה 25.
אז מה בעצם הבנו עד כאן, לגבי החוקיות של גובה מפלס המים המקסימאלי האפשרי בכל נקודה?
הבנו שחוק 1 - בכל נקודה, את המים תמיד יתחום העמוד הגבוה ביותר מצד ימין של אותו המקום + העמוד הגבוה ביותר מצד שמאל של אותו המקום.
חוק 2 - גובה מפלס המים בכל נקודה, תמיד יהיה מוגבל לגובה של העמוד הנמוך ביותר שתוחם את המים באותה הנקודה.
לדוגמה במקרה הנ"ל של [0,100,0,25,0,50,0]
בנקודה של העמוד שבגובה של 25, מפלס המים יהיה 50. כי העמוד הגבוה ביותר מצד ימין, הוא 50 והעמוד הגבוה ביותר מצד שמאל, הוא 100. ולכן המים נתחמים על ידי העמודים של ה 50 מצד ימין ושל ה 100 מצד שמאל.
ובין 2 העמודים הגבוהים ביותר שנמצאים מצדדי הנקודה הנוכחית, מביניהם נצטרך למצוא את העמוד הנמוך ביותר. שהוא הגבול האפשרי של מפלס המים.
שזה בעצם אומר, שאנחנו מצד אחד צריכים למצוא את הנקודה הגבוהה ביותר שתתחום את המים ומצד שני אנחנו צריכים למצוא את הנקודה הנמוכה ביותר, מבין 2 הנקודות הגבוהות ביותר.
שזה בעצם אומר, שבכל נקודה אנחנו נרצה לדעת, מהו העמוד הכי גבוה מצד ימין של אותו המקום וגם מהו העמוד הכי גבוה מצד שמאל של אותו המקום. ואז הגובה הנמוך ביותר, מבין 2 העמודים הגבוהים ביותר, הוא יהיה הגובה המקסימאלי האפשרי של מפלס המים.
אבל איך נוכל לדעת בכל נקודה, מהו העמוד הכי גבוה מצד ימין ומהו העמוד הכי גבוה מצד שמאל, כדי שנוכל לדעת את הגובה המקסימאלי האפשרי של מפלס המים?
תשובה: נעצור כאן לרגע בתהליך וננסה לחשוב על הדברים בצורה אחרת יותר פשוטה. ננסה להבין טוב יותר את המשימה של לחפש בכל נקודה, את העמוד הגבוה ביותר מצד ימין ואת העמוד הגבוה ביותר מצד שמאל.
אז מה בעצם אנחנו מבינים עד כה, אנחנו מבינים שבכל נקודה נצטרך לחשב כמה חישובים, שהם:
1 - מהו העמוד הגבוה ביותר שמצד ימין ביחס לאותה הנקודה הנוכחית?
2 - מהו העמוד הגבוה ביותר שמצד שמאל ביחס לאותה הנקודה הנוכחית?
3 - מבין 2 העמודים האלו, מהו העמוד הנמוך ביותר מביניהם?
ו 3 השאלות האלו, יתנו לנו את מפלס המים האפשרי בנקודה הנוכחית.
אבל האם זאת כל האמת? האם באמת אנחנו תמיד צריכים לעשות את 3 החישובים האלו, כדי לדעת מהו מפלס המים האפשרי בכל נקודה?
ולכאורה התשובה היא שכן. כי אנחנו צריכים לדעת מה הגובה הגבוה ביותר של העמודים שתוחמים את המים וכולי כנ"ל. אבל זאת לא כל האמת. למה?
אז ננסה לדייק את מה שהבנו עד כה. הבנו כי כדי לדעת מה גובה מפלס המים המקסימאלי האפשרי בנקודה כלשהי, לשם כך עלינו לדעת:
1 - מה גובה העמוד הגבוה ביותר מצד ימין של אותה הנקודה הנוכחית
2- מה גובה העמוד הגבוה ביותר מצד שמאל של אותה הנקודה הנוכחית
3 - מה גובה העמוד הנמוך ביותר מבין 2 העמודים הנ"ל
וזה בעצם נותן לנו את גובה מפלס המים המקסימאלי האפשרי בנקודה כלשהי
כאשר, אם נפחית את גובה העמוד עצמו, אז נקבל את כמות המים הכלואים באותה הנקודה.
ונשאל את השאלה הבאה:
האם יהיה נכון לומר, שאם נדע בכל מיקום, את הנקודה הגבוה ביותר מצד ימין ואת הנקודה הגבוה ביותר מצד שמאל, אז נוכל לדעת את גובה מפלס המים כנ"ל? תשובה: כן. הטענה הנ"ל היא אמת.
אבל האם מכך ניתן להסיק שבהכרח צריך לדעת בכל נקודה את גובה 2 הנקודות הגבוהות ביותר שתוחמות את אותה הנקודה? תשובה: לא.
ואני אסביר. למה אנחנו מחפשים את הנקודה הגבוה ביותר, מ 2 הצדדים של הנקודה הנוכחית? למה שלא נסתפק ב 2 נקודות גובה כלשהן, לצידי המיקום הנוכחי שלנו? תשובה: כי אולי מפלס המים יכול להיות גבוה יותר, מאשר 2 הנקודות האקראיות שנמצאות לצד הנקודה הנוכחית שלנו.
לדוגמה במקרה של: [5,4,3,2,1,2,3,4,5] גובה מפלס המים היכן שנמצא העמוד האמצעי, שהוא העמוד בגובה 1, יהיה 5 והוא לא יהיה רק לפי הגובה של העמודים שצמודים אליו. אלא אנחנו חייבים למצוא את 2 הנקודות הגבוהות ביותר משני הצדדים של המיקום הנוכחי שלנו. אבל האם זאת באמת כל האמת?
והתשובה היא, שלא! ולמה, כי בסופו של דבר, מפלס המים מוגבל לגובה של העמוד הנמוך ביותר מבין 2 העמודים ההכי גבוהים שנמצאים לצידי המיקום הנוכחי שלנו.
ומאחר שאנחנו מוגבלים לגובה הנמוך ביותר, של אחד הגבהים הגבוהים ביותר, זה בעצם אומר, שבמקרה כזה לדוגמה
[5,4,3,2,1,200,300,400,500]
אם נדע שמצד שמאל של העמוד האמצעי, העמוד בגובה 1, אם נדע שמצד שמאל שלו, העמוד הגבוה ביותר הוא 5, האם זה ישנה לנו מהו גובה העמוד הגבוה ביותר שלו, מצד ימין. האם זה משנה לנו אם העמוד בגובה של 1, תחום ב 5+200 או ב 5+300 או ב 5+כל מספר אחר שגבוה מהמספר 5?
התשובה היא שלא. כי בכל מקרה מפלס המים לא יהיה גבוה יותר מ 5.
וזה בעצם אומר, שאם אנחנו יודעים מה הגובה הגבוה ביותר מצד 1 כלשהו של המיקום הנוכחי, הרי שאנחנו כבר לא צריכים לדעת מה הגובה של העמוד הגבוה ביותר מהצד שני. אלא אנחנו צריכים לעשות את החישוב הבא:
ניקח לדוגמה את המקרה הבא:
[3,1,0,7,1,3,1,5,0,9,2,5,1,4,0,0,10,1,4,6]
נסתכל לצורך העניין על העמוד השני, שהגובה שלו הוא 1. נבדוק מה הגובה של העמוד הגבוה ביותר שנמצא מצד שמאל שלו. ונראה שזה העמוד הראשון שהוא בגובה של 3.
וזה בעצם אומר, שאנחנו יודעים בוודאות, שמצד שמאל של העמוד השני שלנו, יש עמוד בגובה של 3. דהיינו, אנחנו יודעים בוודאות שלא משנה מה, מפלס המים לא יהיה יותר גבוה מ 3.
אבל האם אנחנו יכולים לדעת בוודאות שמפלס המים במיקום של העמוד השני, יהיה 3? אולי הוא יהיה 2 או 1 או אולי אפילו 0? איך נדע את זה?
אז במה זה תלוי? לשם כך נצטרך לבדוק את הגובה של העמודים שנמצאים בצד הימני של המיקום השני. ואז יש לנו כמה אפשרויות.
1 - אם כל העמודים שנמצאים מהצד הימני, הם נמוכים מ 3, דהיינו, אם העמוד הגבוה ביותר מצד ימין, הוא קטן מ 3, הרי שמפלס המים לא יהיה 3, אלא הוא יהיה מוגבל לגובה של העמוד הגבוה ביותר שנמצא מצד ימין של העמוד השני.
2 - אם מצד ימין של העמוד השני, יש עמוד כלשהו, שהגובה שלו הוא 3 או יותר, דהיינו, שהגובה שלו הוא זהה או גדול מהגובה של העמוד הגבוה ביותר השמאלי ביותר, הרי שאנחנו יכולים לדעת בוודאות שגובה מפלס המים יהיה 3 ולא יותר. לא משנה מה. כי בסוף, המים מוגבלים לגובה של העמוד הנמוך ביותר מבין 2 העמודים הגבוהים ביותר.
דהיינו, במקרה שלנו, אם נסתכל לצד ימין של המיקום השני, הרי שנוכל לראות עמודים גבוהים יותר מ 3. וזה בעצם אומר, שמפלס המים במיקום 2, יהיה לא יותר גבוה מ 3. ואנחנו יודעים את זה בוודאות, גם בלי לדעת מה הגובה הגבוה ביותר מצד ימין, של העמוד שנמצא במיקום השני.
או במילים אחרות, כאשר אנחנו מוצאים את הגובה של העמוד הגבוה ביותר, מצד 1 כלשהו, צד ימין או שמאל, של מיקום כלשהו, הרי שאנחנו לא צריכים למצוא את הגובה של העמוד הגבוה ביותר מהצד שני, אלא אנחנו צריכים לוודא שמהצד השני יש עמוד בגובה זהה או גבוה יותר, מהגובה של העמוד הגבוה ביותר, מהצד שכבר מצאנו.
לדוגמה, אם נגלה שהעמוד הגבוה ביותר מצד ימין הוא 100, אז נצטרך לוודא שמצד שמאל יש עמוד בגובה של 100 או יותר. וזהו. אבל אח"כ לא נצטרך להמשיך לחפש את הגובה של העמוד הגבוה ביותר מצד שמאל. אלא אם לא נמצא עמוד בגובה זהה או גבוה מהעמוד שמצאנו בצד ימין, שאז נצטרך להמשיך לחפש את העמוד הגבוה ביותר גם בצד השני.
אז בהתאם להבנה הזאת, ננסה להסתכל על המקרה הקודם:
[3,1,0,7,1,3,1,5,0,9,2,5,1,4,0,0,10,1,4,6]
נסתכל לצורך העניין על העמוד השני, שהגובה שלו הוא 1. נבדוק מה הגובה של העמוד הגבוה ביותר שנמצא מצד שמאל שלו. ונראה שזה העמוד הראשון שהוא בגובה של 3.
וזה בעצם אומר, שאנחנו יודעים בוודאות, שמצד שמאל של העמוד השני שלנו, יש עמוד בגובה של 3. דהיינו, אנחנו יודעים בוודאות שלא משנה מה, מפלס המים לא יהיה יותר גבוה מ 3.
אבל האם אנחנו יכולים לדעת בוודאות שמפלס המים במיקום של העמוד השני, יהיה 3? אולי הוא יהיה 2 או 1 או אולי אפילו 0? איך נדע את זה?
אז במה זה תלוי? לשם כך נצטרך לבדוק את הגובה של העמודים שנמצאים בצד הימני של המיקום השני. ואז יש לנו כמה אפשרויות.
1 - אם כל העמודים שנמצאים מהצד הימני, הם נמוכים מ 3, דהיינו, אם העמוד הגבוה ביותר מצד ימין, הוא קטן מ 3, הרי שמפלס המים לא יהיה 3, אלא הוא יהיה מוגבל לגובה של העמוד הגבוה ביותר שנמצא מצד ימין של העמוד השני.
2 - אם מצד ימין של העמוד השני, יש עמוד כלשהו, שהגובה שלו הוא 3 או יותר, דהיינו, שהגובה שלו הוא זהה או גדול מהגובה של העמוד הגבוה ביותר השמאלי ביותר, הרי שאנחנו יכולים לדעת בוודאות שגובה מפלס המים יהיה 3 ולא יותר. לא משנה מה. כי בסוף, המים מוגבלים לגובה של העמוד הנמוך ביותר מבין 2 העמודים הגבוהים ביותר.
דהיינו, במקרה שלנו, אם נסתכל לצד ימין של המיקום השני, הרי שנוכל לראות עמודים גבוהים יותר מ 3. וזה בעצם אומר, שמפלס המים במיקום 2, יהיה לא יותר גבוה מ 3. ואנחנו יודעים את זה בוודאות, גם בלי לדעת מה הגובה הגבוה ביותר מצד ימין, של העמוד שנמצא במיקום השני.
או במילים אחרות, כאשר אנחנו מוצאים את הגובה של העמוד הגבוה ביותר, מצד 1 כלשהו, צד ימין או שמאל, של מיקום כלשהו, הרי שאנחנו לא צריכים למצוא את הגובה של העמוד הגבוה ביותר מהצד שני, אלא אנחנו צריכים לוודא שמהצד השני יש עמוד בגובה זהה או גבוה יותר, מהגובה של העמוד הגבוה ביותר, מהצד שכבר מצאנו.
לדוגמה, אם נגלה שהעמוד הגבוה ביותר מצד ימין הוא 100, אז נצטרך לוודא שמצד שמאל יש עמוד בגובה של 100 או יותר. וזהו. אבל אח"כ לא נצטרך להמשיך לחפש את הגובה של העמוד הגבוה ביותר מצד שמאל. אלא אם לא נמצא עמוד בגובה זהה או גבוה מהעמוד שמצאנו בצד ימין, שאז נצטרך להמשיך לחפש את העמוד הגבוה ביותר גם בצד השני.
אז בהתאם להבנה הזאת, ננסה להסתכל על המקרה הקודם:
[3,1,0,7,1,3,1,5,0,9,2,5,1,4,0,0,10,1,4,6]
ונסתכל על העמוד הימני ביותר, העמוד במיקום 20 שהגובה שלו הוא 6. וננסה להבין מה אנחנו יכולים להסיק מכך? האם יש משהו שאנחנו יכולים להסיק מכך בוודאות?
אז התשובה היא, שאולי כן. כי בעצם אנחנו יודעים שבמיקום 20, העמוד הגבוה ביותר הוא בגובה של 6. דהיינו, אנחנו כבר יכולים לדעת בוודאות, שלא משנה מה, גובה המים במיקום 20, לא יהיה גבוה יותר מ 6. כי זה העמוד הגבוה ביותר שנמצא בצד ימין. אבל האם גובה המים יהיה 6 או פחות מ 6, איך נדע?
זה כמובן תלוי בגובה של העמודים שנמצאים מצד שמאל של העמוד הימני ביותר.
ואני אדייק, שבפועל בוודאות שלא יהיו מים כלואים, לא במיקום הראשון ולא במיקום האחרון, בכל תרחיש. כי המים הכלואים, חייבים להיות בין 2 עמודים כלשהם. אבל כרגע לצורך הניתוח, אני מתעלם מזה כרגע ומתייחס לכל מיקום, כולל הראשון והאחרון, כאילו הם מיקומים רגילים.
אז בעצם מכך שאנחנו יודעים שבצד ימין, במיקום 20, הגובה הגבוה ביותר הוא 6, הרי שאנחנו יודעים בוודאות שלא יהיו שם מים יותר מגובה של 6. אבל אולי יהיו שם פחות מים בגובה יותר נמוך? אז הרי שכבר יש לנו וודאות חלקית כלשהי. אבל עדיין אין אפשרות להתקדם איתה למסקנה וודאית כלשהי.
אז נסתכל על הנקודה הראשונה מצד שמאל, העמוד הראשון, שהוא בגובה של 3. האם מכך אנחנו יכולים להסיק משהו בוודאות? התשובה היא, שכן!
כי אנחנו יודעים שהעמוד הגבוה ביותר מצד שמאל, דהיינו, העמוד הראשון הוא בגובה 3. ולכן אנחנו יודעים בוודאות שגובה המים לא יהיה יותר גבוה מ 3. אבל האם הוא יהיה אולי פחות מ 3? התשובה היא שלא. הוא יהיה בדיוק 3.
ולמה? כי אנחנו יודעים גם שמצד ימין של המיקום הראשון, יש עמוד בגובה של 6, שהוא העמוד הימני ביותר כנ"ל.
או במילים אחרות, מכך שאנחנו יודעים שהעמוד השמאלי ביותר, הוא 3 והעמוד הימני ביותר הוא 6, הרי שאנחנו יודעים בוודאות, שבמיקום השמאלי הראשון הגובה יהיה בדיוק 3. ולגבי העמוד הימני, אנחנו לא יודעים עדיין מה יהיה הגובה המדוייק. כי הוא אומנם לא יהיה יותר מ 6, אבל אולי הוא יהיה 5 או אולי 4. למרות שאנחנו כבר יודעים שבוודאות הוא יהיה לפחות 3.
דהיינו, לגבי מיקום 1 השמאלי ביותר, אנחנו יודעים שגובה המים בוודאות הוא 3.
לגבי המיקום 20 הימני ביותר, אנחנו יודעים שגובה המים יהיה בין 3 לבין 6. לא פחות מ 3 ולא יותר מ 6.
וכך הגענו לפתרון הבא:
ובלי קשר אנחנו יודעים, שלא משנה מה, במיקום הימני והשמאלי ביותר, תמיד כמות המים הכלואים, תהיה 0, בכל תרחיש. כי אין 2 עמודים שתוחמים את המיקום הקיצוני ביותר כנ"ל.
ולכן נסמן
וזה בעצם אומר, שיש לנו וודאות לגבי המיקום הראשון מצד שמאל, בלי לרוץ אפילו פעם אחת על כל הרשימה, אלא מספיק לדעת מה הערך של העמוד הימני ביותר ושל השמאלי ביותר, כדי לפתור בוודאות את הקצה השמאלי ביותר או הימני ביותר, כנ"ל.
אז בעצם הנקודה הוודאית ביותר כרגע, היא מיקום מספר 1, שבו אנחנו יודעים בוודאות את גובה מפלס המים ואת כמות המים הכלואים.
אז עכשיו נעבור לנקודה הקרובה ביותר, לנקודה במיקום מספר 2, שהגובה שם הוא 1. ונשאל, האם יש משהו שאנחנו יכולים לדעת שם בוודאות?
והתשובה היא, שכן! כי בוודאות שבמיקום השמאלי של המיקום השני, דהיינו, במיקום הראשון, בוודאות שגובה מפלס המים הוא 3. ובמיקום השני גובה העמוד הוא 1. דהיינו, גובה העמוד הוא לא גבוה יותר מגובה מפלס המים שנמצא בצד שמאל. ולכן גם במיקום 2, גובה מפלס המים, יהיה בוודאות 3. וכך הגענו לכאן.
וכך נמשיך גם למיקום מספר 3 ונקבל את התוצאה הזאת:
ועכשיו נעבור למיקום מספר 4, שבו העמוד הוא בגובה של 7.
אז אנחנו מבינים שמפלס המים כבר לא חייב להיות 3, כי מצד שמאל יש לנו עמוד יותר גבוה מ 3. אנחנו מבינים גם שמפלס המים יכול להיות 7. אנחנו מבינים גם שמפלס המים לא יכול להיות יותר מ 7. כי 7 זה המספר הגדול ביותר מצד שמאל, ביחס למיקום הרביעי שבו אנחנו נמצאים. אבל האם מפלס המים יהיה 7 אולי פחות?
אז אנחנו יודעים שבצד ימין יש עמוד בגובה של 6. שזה בעצם אומר, שבמיקום 4, מפלס המים יהיה לא יותר מ 7 ולא פחות מ 6. דהיינו, או 6 או 7. אבל אין לנו וודאות לגבי מה יהיה גובה מפלס המים במיקום 4.
אבל אנחנו כן יכולים לדעת בוודאות מה יהיה גובה מפלס המים במיקום 20. כי יש שם עמוד בגובה 6 ומצד שמאל שלו יש עמוד בגובה 7. דהיינו, מפלס המים במיקום 20, יהיה 6.
כך:
אז כרגע יש לנו וודאות לגבי מיקום 20, ויש לנו וודאות חלקית לגבי מיקום 4. ולכן נמשיך במיקום 19, וננסה לראות האם ומה אפשרי להסיק שם.
ושם גובה המים הוא 4, דהיינו, בוודאות שהמפלס יהיה שם 6. וכמות המים הכלואים תהיה 2 כך:
ואז נמשיך למיקום מספר 18 ונגיע לזה:
ועכשיו נעבור למיקום מספר 17, ונראה שיש שם עמוד בגובה של 10. דהיינו, נוכל לדעת בוודאות, שמפלס המים שם לא יהיה יותר מ 10, והוא גם לא יהיה פחות מ 7, שזאת הנקודה הגבוה ביותר שידועה לנו עד כה מצד שמאל. ולכן כרגע אנחנו יכולים לדעת שהמים במיקום 17, יהיו בין 7 לבין 10.
אבל נוצרה לנו וודאות, לגבי מיקום 4. שיש שם עמוד בגובה של 7 ומצד ימין יש במיקום 17 עמוד בגובה 10. ולכן בוודאות נוכל לדעת שבמיקום 4, יש מים בגובה 7. לא יותר ולא פחות.
וכך הגענו לכאן:
וכך נמשיך הלאה עד שנפתור את כל התרגיל, כך:
אז איך בעצם פתרנו את השאלה? קודם כל חילקנו לחלקים, לנסות למצוא איך לדעת מה גובה מפלס המים בכל נקודה, בלי קשר לשאלה כמה מים כלואים שם.
אחר כך ניסינו להבין בדיוק את החוקיות של איך לחשב את גובה מפלס המים, במדויק. וברגע שהבנו את הנוסחה במדויק, מכאן עברנו על המיקום הראשון מצד ימין והראשון מצד שמאל וניסינו להבין, האם יש משהו אפילו הקטן ביותר, שהוא בטוח נכון?!
וראינו, שכן יש משהו שהוא בטוח נכון. ובכל פעם סימנו משהו אחר שהוא בטוח נכון. וכך פתרנו את כל התרגיל, בריצה על הרשימה מ 2 הצדדים בו זמנית, כאשר כל צד נותן וודאות או לגבי עצמו או לגבי הצד השני.
לסיכום: לחלק לחלקים הכי קטנים ולנסות להבין האם ומה בטוח נכון.
050-3331-331