... מים מאשר הגובה של ה 25. אז מה בעצם הבנו עד כאן, לגבי החוקיות של גובה מפלס המים המקסימאלי האפשרי בכל נקודה? הבנו שחוק 1 - בכל נקודה, את המים תמיד יתחום העמוד
הגבוה ביותר מצד ימין של אותו המקום + העמוד
הגבוה ביותר מצד שמאל של אותו המקום. חוק 2 - גובה מפלס המים בכל נקודה, תמיד יהיה מוגבל לגובה של העמוד הנמוך ביותר שתוחם את המים באותה הנקודה. לדוגמה במקרה הנל של (0,100,0,25,0,50,0) בנקודה של העמוד שבגובה של 25, מפלס המים יהיה 50. כי העמוד
הגבוה ביותר מצד ימין, הוא 50 והעמוד
הגבוה ביותר מצד שמאל, הוא 100. ולכן המים נתחמים על ידי העמודים של ה 50 מצד ימין ושל ה 100 מצד שמאל. ובין 2 העמודים הגבוהים ביותר שנמצאים מצדדי הנקודה הנוכחית, מביניהם ... האפשרי של מפלס המים? תשובה: נעצור כאן לרגע בתהליך וננסה לחשוב על הדברים בצורה אחרת יותר פשוטה. ננסה להבין טוב יותר את המשימה של לחפש בכל נקודה, את העמוד
הגבוה ביותר מצד ימין ואת העמוד
הגבוה ביותר מצד שמאל. אז מה בעצם אנחנו מבינים עד כה, אנחנו מבינים שבכל נקודה נצטרך לחשב כמה חישובים, שהם: 1 - מהו העמוד
הגבוה ביותר שמצד ימין ביחס לאותה הנקודה הנוכחית? 2 - מהו העמוד
הגבוה ביותר שמצד שמאל ביחס לאותה הנקודה הנוכחית? 3 - מבין 2 העמודים האלו, מהו העמוד הנמוך ביותר מביניהם? ו 3 השאלות האלו, יתנו לנו את מפלס המים האפשרי בנקודה הנוכחית. ... זאת כל האמת? האם באמת אנחנו תמיד צריכים לעשות את 3 החישובים האלו, כדי לדעת מהו מפלס המים האפשרי בכל נקודה? ולכאורה התשובה היא שכן. כי אנחנו צריכים לדעת מה הגובה
הגבוה ביותר של העמודים שתוחמים את המים וכולי כנל. אבל זאת לא כל האמת. למה? אז ננסה לדייק את מה שהבנו עד כה. הבנו כי כדי לדעת מה גובה מפלס המים המקסימאלי האפשרי בנקודה כלשהי, לשם כך עלינו לדעת: 1 - מה גובה העמוד
הגבוה ביותר מצד ימין של אותה הנקודה הנוכחית 2- מה גובה העמוד
הגבוה ביותר מצד שמאל של אותה הנקודה הנוכחית 3 - מה גובה העמוד הנמוך ביותר מבין 2 העמודים הנל וזה בעצם נותן לנו את גובה מפלס המים המקסימאלי האפשרי בנקודה כלשהי כאשר, אם נפחית את גובה העמוד עצמו, אז נקבל את כמות המים הכלואים באותה הנקודה. ונשאל את השאלה הבאה: האם יהיה נכון לומר, שאם נדע בכל מיקום, את הנקודה
הגבוה ביותר מצד ימין ואת הנקודה
הגבוה ביותר מצד שמאל, אז נוכל לדעת את גובה מפלס המים כנל? תשובה: כן. הטענה הנל היא אמת. אבל האם מכך ניתן להסיק שבהכרח צריך לדעת בכל נקודה את גובה 2 הנקודות הגבוהות ביותר שתוחמות את אותה הנקודה? תשובה: לא. ואני אסביר. למה אנחנו מחפשים את הנקודה
הגבוה ביותר, מ 2 הצדדים של הנקודה הנוכחית? למה שלא נסתפק ב 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. דהיינו, ... נצטרך לבדוק את הגובה של העמודים שנמצאים בצד הימני של המיקום השני. ואז יש לנו כמה אפשרויות. 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. דהיינו, ...