LeetCode "42. Trapping Rain Water"が再帰関数で解けなかった話

LeetCode "42. Trapping Rain Water"に挑戦したものの、Timelimit Exceededで解けませんでした。

問題

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

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

方針

数字の並び順に意味があるので、「とりあえずソートしておく」はこの問題では使えません。
与えられたn個の非負整数から、二次元の配列として地図を描きます。
それぞれのバーの各高さについて、右側に探索を進めていきます。探索の結果、別のバーにぶつかった場合には、その間の成分1つにつき1つ、水量を加算します。
探索には再帰関数を用います。

提出したコード

class Solution:
    def __init__(self):
        # self.res: 最終的に返される値
        self.res = 0    

    def trap(self, height: List[int]) -> int:
        #地図を作る。
        #地図の高さを決めるために、heightの最大値max_heightを求める。

        max_height = max(height)


        # map_:地図
        # 0: 何もない場所,　2:壁
        # 壁が1出ないのは、3を水とし、あとで、x%2したものの合計を出して、それを積水量としたかったことの痕跡。　
        map_ = [[0 for j in range(max_height)] for i in range(len(height))]

        for i in range(len(map_)):
            for j in range(height[i]):
                map_[i][j] = 2

        def search(i, j):
            # 限界を迎えそうになっても壁に当たらなかったら、その高さiでは水はたまらない。
            if i + 1 > len(map_) - 1:
                return False

            # 隣のマスが壁なら、Trueを返す。
            if map_[i + 1][j] == 2:
                # 今いるマスに何もないなら、水量を加算する。
                if map_[i][j] == 0:
                   self.res += 1
                return True

            # 隣の隣の……と探索を続けて壁に当たるなら、Trueを返す。
            if search(i + 1, j):
                # 今いるマスに何もないなら、水量を加算する
                if map_[i][j] == 0:
                   self.res += 1
                return True

            return False

        # heightの各elementについて、それが0以上である場合、探索を行う。
        for i, element in enumerate(height):
            if element > 0:
                for j in range(element):
                    search(i, j)

        return self.res

結果:Time Limit Exceeded

反省

探索を、バー単位ではなく、勝手に設定した二次元配列の要素単位で行っていることが、Time Limit Exceededのおそらくの原因です。
バー単位での水量を求める問題には、このような例があります。
https://leetcode.com/problems/container-with-most-water/
明日はこれをヒントにチャレンジしてみます。