חידת LeetCode Solution - Trapping Rain Water, פתרון ליטקוד, LeetCode Solution, איך לפתור שאלות ב LeetCode? איך לפתור חידת LeetCode? מדעי המחשב, תכנות מחשבים, איך להתקבל לעבוד בהייטק? איך ללמוד תכנות מחשבים? איך להיות מתכנת? איך לעבור ראיון טכני? איך להתכונן לראיון עבודה בהייטק? תרגול שאלות ליטקוד כהכנה לראיון, איך להיות מתכנת מחשבים? איך לעבוד בפיתוח תוכנה? איך להתכונן לראיונות כתיבת קוד? איך לפתור חידת היגיון? חידות היגיון... עמוד בפני עצמו. דהיינו, ננסה להתמקד בלהבין את הנוסחה, איך לדעת כמה מים נכנסים מעל כל עמוד בודד. ואיך אפשרי לדעת כמה מים נכנסים במקום של כל אחד מהעמודים בפני עצמו? אז גם את השאלה הזאת נחלק אותה לחלקים. ומי שיתבונן יראה, כי כמות המים שנכנסת מעל כל עמוד, תלויה ב 2 גורמים, שהם: 1 - גובה מפלס המים האפשרי במיקום של העמוד. 2 - גובה העמוד עצמו. שאז אם ניקח את גובה מפלס המים האפשרי באותו מיקום ונפחית ממנו את גובה העמוד שבאותו מיקום, אז נוכל לקבל את כמות המים הכלואים מעל העמוד. לדוגמה בדוגמה לעיל, עמוד מספר 7, הגובה שלו הוא 1, גובה מפלס המים האפשרי באותו מיקום הוא 2 (בגלל העמוד במיקום 8 ובמיקום 4). ולכן כמות המים הכלואים מעל העמוד, היא 1. או במילים אחרות, אנחנו בעצם מבינים, כי כדי לדעת כמה מים כלואים במיקום של העמוד, לשם כך קודם כל צריכים לדעת את גובה מפלס המים האפשרי במיקום של העמוד. ורק אחר כך להפחית ממנו את גובה העמוד הנוכחי וככה לדעת את כמות המים. ורק אחר כך לסכום את כל הכמויות כדי לדעת את הכמות הכללית. ולכן בשלב הראשון נצטרך לחשב את גובה מפלס המים האפשרי בכל נקודה מעל כל עמוד. דהיינו, במקום לנסות לחשוב, כמה מים כלואים יש בכל נקודה, ננסה לחשוב, מה גובה המים המקסימאלי האפשרי בכל נקודה. ואיך ניגשים לזה? איך יודעים מה גובה מפלס המים האפשרי מעל כל עמוד? אז כדי לדעת מה גובה מפלס המים המקסימאלי האפשרי מעל כל עמוד, לשם כך נצטרך לדעת את החוקיות של מפלס המים. איך היא עובדת? במה תלוי גובה מפלס המים האפשרי בכל נקודה? אז כמובן שיש לנו את חוק כלים שלובים, שאומר שפני המים תמיד יהיו באותו הגובה. בנוסף יש לנו כמובן גם את האילוץ של הגובה של העמודים, שאמורים להחזיק את המים. ובכך בעצם תלוי גובה פני המים האפשרי בכל נקודה. דהיינו, גובה מפלס המים האפשרי, תלוי בגובה העמודים שתוחמים ושכולאים בתוכם את המים ובחוק כלים שלובים, שאומר שתמיד המים יהיו באותו הגובה. אבל איך נוכל לחשב את גובה פני המים האפשרי? מהי הנוסחה לכך? אז איך יודעים מהי הנוסחה לחשב את גובה פני המים האפשרי בכל נקודה? לשם כך ננסה שוב לחלק לחלקים ולחפש את המקרה הפשוט ביותר וכך ננסה להבין את החוקיות. אז מהו המקרה הפשוט ביותר? המקרה ... כי כדי לאגור מים צריך 2 עמודים שיחזיקו ביניהם את המים. עכשיו כדי לנסות להבין את החוקיות של גובה האפשרי של מפלס המים, נלך למקרה קצת יותר מורכב, שבו יש לנו 2 עמודים צמודים אחד לשני באותו הגובה. לדוגמה 2 עמודים בגובה 100. ... יהיה בהתאם לגובה של העמוד הנמוך ביותר שתוחם את המים. אבל האם זאת כל האמת? האם יהיה נכון לומר, שהגובה האפשרי של המים, תמיד יהיה בהתאם לגובה של העמוד הנמוך ביותר שתוחם אותו? אז נבדוק את המקרה הבא, שיש בו: עמוד של 100, מקום ריק, עמוד של ... ה 25, יותר מים מאשר הגובה של ה 25. אז מה בעצם הבנו עד כאן, לגבי החוקיות של גובה מפלס המים המקסימאלי האפשרי בכל נקודה? הבנו שחוק 1 - בכל נקודה, את המים תמיד יתחום העמוד הגבוה ביותר מצד ימין של אותו המקום + העמוד הגבוה ביותר מצד שמאל של ... הגבוהים ביותר שנמצאים מצדדי הנקודה הנוכחית, מביניהם נצטרך למצוא את העמוד הנמוך ביותר. שהוא הגבול האפשרי של מפלס המים. שזה בעצם אומר, שאנחנו מצד אחד צריכים למצוא את הנקודה הגבוהה ביותר שתתחום את המים ומצד שני אנחנו צריכים למצוא את ... שמאל של אותו המקום. ואז הגובה הנמוך ביותר, מבין 2 העמודים הגבוהים ביותר, הוא יהיה הגובה המקסימאלי האפשרי של מפלס המים. אבל איך נוכל לדעת בכל נקודה, מהו העמוד הכי גבוה מצד ימין ומהו העמוד הכי גבוה מצד שמאל, כדי שנוכל לדעת את הגובה המקסימאלי האפשרי של מפלס המים? תשובה: נעצור כאן לרגע בתהליך וננסה לחשוב על הדברים בצורה אחרת יותר פשוטה. ננסה להבין טוב יותר את המשימה של לחפש ... 3 - מבין 2 העמודים האלו, מהו העמוד הנמוך ביותר מביניהם? ו 3 השאלות האלו, יתנו לנו את מפלס המים האפשרי בנקודה הנוכחית. אבל האם זאת כל האמת? האם באמת אנחנו תמיד צריכים לעשות את 3 החישובים האלו, כדי לדעת מהו מפלס המים האפשרי בכל נקודה? ולכאורה התשובה היא שכן. כי אנחנו צריכים לדעת מה הגובה הגבוה ביותר של העמודים שתוחמים את המים וכולי כנל. אבל זאת לא כל האמת. למה? אז ננסה לדייק את מה שהבנו עד כה. הבנו כי כדי לדעת מה גובה מפלס המים המקסימאלי האפשרי בנקודה כלשהי, לשם כך עלינו לדעת: 1 - מה גובה העמוד הגבוה ביותר מצד ימין של אותה הנקודה הנוכחית 2- מה גובה העמוד הגבוה ביותר מצד ... 3 - מה גובה העמוד הנמוך ביותר מבין 2 העמודים הנל וזה בעצם נותן לנו את גובה מפלס המים המקסימאלי האפשרי בנקודה כלשהי כאשר, אם נפחית את גובה העמוד עצמו, אז נקבל את כמות המים הכלואים באותה הנקודה. ונשאל את השאלה הבאה: האם יהיה נכון ... וודאות לגבי מיקום 20, ויש לנו וודאות חלקית לגבי מיקום 4. ולכן נמשיך במיקום 19, וננסה לראות האם ומה אפשרי להסיק שם. ושם גובה המים הוא 4, דהיינו, בוודאות שהמפלס יהיה שם 6. וכמות המים הכלואים תהיה 2 כך: ואז נמשיך למיקום מספר 18 ונגיע ...