Pythonで雨水をトラップするアルゴリズムを解説【スタックを使った実装】

問題の概要

n個の非負整数からなる配列を考えます。この配列は、各バーの幅が1である「標高マップ」を表しており、雨が降ったあとにこの地形へ最大でどれだけの水を溜められるかを計算するのが目的です。いわゆる「Trapping Rain Water（雨水をトラップする）」として知られる有名なアルゴリズム問題です。

イメージは以下のようになります。

上の図では水たまり（青い部分）が6マスあるため、答えは6になります。

スタックを使った解法の考え方

この問題はスタックを利用すると効率的に解けます。各位置のインデックスをスタックで管理し、現在のバーがスタックの頂点にあるバーより高い場合には、その間に水が溜まっている可能性があるため、スタックから要素を取り出しながら水量を積算していくのが基本のアイデアです。

アルゴリズムの手順

1. スタック st を用意し、water := 0、i := 0 で初期化します。
2. i が height の長さ未満である間、以下を繰り返します。
   • スタックが空、または height[スタックの頂点] >= height[i] の場合：i をスタックにプッシュし、i を1増やします。
   • それ以外の場合：
     • x := スタックの頂点の要素を取り出し、スタックから削除します。
     • スタックが空でない場合は、さらに以下を実行します。
       • temp := min(height[スタックの頂点], height[i])
       • dist := i − スタックの頂点 − 1
       • water := water + dist × (temp − height[x])
3. 最後に water を返します。

Pythonでの実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution(object):
    def trap(self, height):
        stack = []
        water = 0
        i = 0
        while i < len(height):
            if len(stack) == 0 or height[stack[-1]] >= height[i]:
                stack.append(i)
                i += 1
            else:
                x = stack[-1]
                stack.pop()
                if len(stack) != 0:
                    temp = min(height[stack[-1]], height[i])
                    dist = i - stack[-1] - 1
                    water += dist * (temp - height[x])
        return water

ob = Solution()
print(ob.trap([0,1,0,2,1,0,1,3,2,1,2,1]))

入力

[0,1,0,2,1,0,1,3,2,1,2,1]

出力

6

計算量について

各インデックスは最大でも一度しかスタックへのプッシュ・ポップが行われないため、時間計算量は O(n) です。また、スタックに保持される要素数は配列の長さに依存するため、空間計算量も O(n) となります。全探索的なアプローチよりも大幅に効率よく解けるのが、このスタックを使った手法の魅力です。