昨日、LeetCode "42. Trapping Rain Water"に挑戦したものの、Timelimit Exceededで解けませんでした。
LeetCodeは一部の問題について無料で解答例の方針とコードを見ることができます。
この問題については、解答例のコードがC++で与えられています。
その方針のうち、Approach 2が私にとって理解しやすかったです。
私はPythonしかできないので、PythonでApproach 2を実装します。

問題

こちらから挑戦できます。
https://leetcode.com/problems/trapping-rain-water/

n個の非負整数が与えられています。それらの非負整数は、標高の地図を表しています。（各非負整数が表す）バーの幅を１とします。この標高地図は、降雨の後にどれだけの水をためられるでしょうか。計算してください。

昨日の失敗

LeetCode "42. Trapping Rain Water"が再帰関数で解けなかった話
https://qiita.com/Takeshi_Sue/items/ed0e58c5fc8eaba3fd46

失敗の原因は、再帰関数で挑んだためではないでしょう。失敗の原因は、与えられた一次元の配列を元に標高と水嵩を表す二次元の配列を作ったことにより計算時間を食ったためだと考えています。

Approach 2

ここから解法を見ることができます。
https://leetcode.com/problems/trapping-rain-water/solution/

Approach 2を私なりに解釈すると、このような形です。

•壁の左側にだけ水素を撒く
•壁の右側にだけ酸素を撒く
•それらを爆発させると、水素または酸素のうち高さの低いほうに合わせて、水が出来上がる
•水を数えて、答えとする。

提出したコード

class Solution:
    
    def trap(self, height: List[int]) -> int:
        # len(height)は何回も使いそうなので、あらかじめ取得してしまいます。
        len_height = len(height)

        # 水素を充満させた結果を記録する配列、h2_heightを用意します。
        h2_height = [0 for _ in range(len_height)]
        # cur_max：　forで繰り返していくなかで、その時点での最大の壁の高さを記録します。
        cur_max = 0

        # 壁より右側に水素を充満させます
        for i in range(len_height):
            cur_max = max([height[i], cur_max])
            h2_height[i] = cur_max

        # 酸素を充満させた結果を記録する配列、o_heightを用意します。
        o_height = [0 for _ in range(len_height)]
        # cur_max：　forで繰り返していくなかで、その時点での最大の壁の高さを記録します。
        cur_max = 0

        # 壁より左側に酸素を充満させます
        for i in reversed(range(len_height)):
            cur_max = max([height[i], cur_max])
            o_height[i] = cur_max

        # res: 最終的に返す値
        res = 0

        for h2, oxigen, wall in zip(h2_height, o_height, height):
            # min([h2, oxigen]):水素と酸素があった場所、つまりは水がある場所
            # wall: 水の位置を底上げしている壁
            res += min([h2, oxigen]) - wall

        return res

結果：解答通りにやってるので、もちろん成功します。

感想

めっちゃ悩んで解いて間違ったものの解答が、実はこんなに簡単だと、なかなかに気分がわるいね！
ストゼロ飲んで寝よ！！！！！！！！！