42. Trapping Rain Water

Dobro jutro.

Evo, fatnje in dekline. Da ne bo danes aktualna samo politika in pripadajoči kurberaj...

Na internetih sem našel sledečo nalogo:

42. Trapping Rain Water

https://leetcode.com/problems/trapping-...

Ker sem bil pri reševanju naloge neuspešen, sem šel iskat po internetih in našel rešitev (prvi primer) na sledeči strani:

https://www.geeksforgeeks.org/trapping-...

Pogledal sem si primer, napisan v programskem jeziku Python, in napisal praktično isti primer "malo po moje":

height_elements = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];

# height_elements = [0, 1, 0, 2];

# height_elements = [2 ,1, 0, 1, 2];

# height_elements = [2, 1, 5, 3, 1, 0, 4];

total = 0;

res = 0

print(height_elements);

for i in range(1, len(height_elements) - 1):

    left_elements = height_elements[0 : i];

    right_elements = height_elements[i + 1:];

    print(str(left_elements) + " " + str(height_elements[i]) + " " + str(right_elements) + " ", end="");

    max_left = max(left_elements);

    max_rigth = max(right_elements);

    sum = (min(max_left, max_rigth) - height_elements[i]);

    if sum > -1:

        print("sum = " + str(sum), end="");

    else:

        print("sum =" + str(sum), end="");

    res += (min(max_left, max_rigth) - height_elements[i]);

    if res > -1:

        print(" res = " + str(res), end="");

    else:

        print(" res =" + str(res), end="");

    if sum > 0:

        total = total + sum;

    print(" total = " + str(total));

print("res = " + str(res));

print("total = " + str(total));

Output:

[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
[0] 1 [0, 2, 1, 0, 1, 3, 2, 1, 2, 1] sum =-1 res =-1 total = 0
[0, 1] 0 [2, 1, 0, 1, 3, 2, 1, 2, 1] sum = 1 res = 0 total = 1
[0, 1, 0] 2 [1, 0, 1, 3, 2, 1, 2, 1] sum =-1 res =-1 total = 1
[0, 1, 0, 2] 1 [0, 1, 3, 2, 1, 2, 1] sum = 1 res = 0 total = 2
[0, 1, 0, 2, 1] 0 [1, 3, 2, 1, 2, 1] sum = 2 res = 2 total = 4
[0, 1, 0, 2, 1, 0] 1 [3, 2, 1, 2, 1] sum = 1 res = 3 total = 5
[0, 1, 0, 2, 1, 0, 1] 3 [2, 1, 2, 1] sum =-1 res = 2 total = 5
[0, 1, 0, 2, 1, 0, 1, 3] 2 [1, 2, 1] sum = 0 res = 2 total = 5
[0, 1, 0, 2, 1, 0, 1, 3, 2] 1 [2, 1] sum = 1 res = 3 total = 6
[0, 1, 0, 2, 1, 0, 1, 3, 2, 1] 2 [1] sum =-1 res = 2 total = 6
res = 2
total = 6

Tisti, kar mi zaenkrat še ne gre v račun, je ukaz (njihov primer) na liniji 18 in 19:

# Update the maximum water
res += (min(left, right) - arr[i])

Pri meni ne deluje, ker prišteva tudi negativne številke. Kar pa naj ne bi počel. To sedaj iščem, kaj je drugače.

----------------------

UPDATE

Zgleda sem rešil. Popravil sem, kaj predstavlja left in right array. Kot kaže, moreta ta dva array-a poleg tistega, kar je levo ali desno od trenutne pozicije, vsebovati tudi element na sami poziciji.

Se pravi, če je array [1, 2, 3, 4, 5] in smo na sredini (na 3-ki), je left array [1, 2, 3], right array pa [3, 4, 5].

left_elements = height_elements[0 : i + 1];

right_elements = height_elements[i:];

As always... well done.