נתון כלי לצבירת מי גשם. חתך הכלי מתואר על ידי מערך הגבהים heights. למשל, עבור מערך הגבהים {2, 1, 1, 4, 1, 1, 2, 3}
צורת הכלי היא:
וכמות הגשם שניתן לצבור בכלי מיוצגת על ידי המשבצות הכחולות עם המספרים:
| 3 | 2 | 1 | |||||
| 7 | 6 | 5 | 4 | ||||
בהינתן מערך גבהים heights יש להחזיר את כמות הגשם שניתן לצבור בכלי עם מערך גבהים נתון.
למשל, עבור הכלי לעיל, ניתן לצבור 7 יחידות גשם (המשבצות המסומנות).
רמז: יש לחשב בכל מקום בכלי מה גובה העמודה המקסימלית / המינימלית מימינו ומשמאלו.
השיטה צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום.
כל הערכים במערך (הגבהים) הם חיוביים ממש (גדולים מאפס).
heights = [2, 1, 1, 4, 1, 1, 2, 3]
7
הסבר: בכלי זה ניתן לצבור 7 יחידות גשם, כפי שמודגם בתמונה
heights = [1, 2, 3, 4, 1]
0
הסבר: בכלי זה לא ניתן לצבור גשם כלל כי אין שקעים שיכולים להכיל מים
heights = [3, 0, 2, 0, 4]
7
הסבר: ניתן לצבור 3 יחידות מים בעמדה 1 ו-4 יחידות מים בעמדה 3
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
6
הסבר: בכלי המורכב יותר הזה, מצטברים 6 יחידות גשם במספר שקעים שונים
heights = [4, 2, 0, 3, 2, 5]
9
הסבר: המים מצטברים בשקעים השונים בגבהים שונים, סה"כ 9 יחידות
heights = [5, 4, 1, 2]
1
הסבר: ניתן לצבור יחידת מים אחת בלבד בעמדה 2
heights = [5, 2, 1, 2, 1, 5]
14
הסבר: מבנה סימטרי עם דפנות גבוהות בקצוות מאפשר צבירת הרבה מים
heights = [1, 1, 1, 1]
0
הסבר: כאשר כל העמודות באותו גובה, לא ניתן לצבור מים
קלט:
heights = [2, 1, 1, 4, 1, 1, 2, 3]
הפלט המבוקש:
7