Trapping Rain Water：スタックとTwo-Pointer
水平な層を計算する単調スタック手法と、垂直な柱を計算するtwo-pointer手法の両方でtrapping-rain-waterを解きます。
「Trapping Rain Water：スタックとTwo-Pointer」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
問題：Trapping Rain Water
Trapping Rain Water（LeetCode 42）は、面接で最もよく知られた問題の一つです。各棒の幅が1である標高マップを表す n 個の非負整数が与えられたとき、雨が降った後に棒の間に溜まる水の量を計算します。両側にある高い棒の間の谷に水が溜まります。
各位置 i での水位は min(max_left[i], max_right[i]) - height[i] です。これが負の場合、水は溜まりません（棒が少なくとも一方の境界より高いためです）。解法は3つあります。事前計算配列を使う O(n)/O(n)、二つのポインタを使う O(n)/O(1)、単調スタックを使う O(n)/O(n) です。
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
# Water trapped at each position:
# pos 2: min(1,3)-0=1
# pos 4: min(2,3)-1=1
# pos 5: min(2,3)-0=2
# pos 6: min(2,3)-1=1
# pos 9: min(3,2)-1=1
# Total = 6
print('height:', height)
print('Expected trapped water: 6')
# Visualise
max_h = max(height)
for row in range(max_h, 0, -1):
line = ''
for h in height:
line += '#' if h >= row else ' '
print(line)アプローチ1：最大値配列の事前計算
素直な解法は、時間計算量 O(n)、空間計算量 O(n) で、2つの配列を事前計算します。max_left[i] はインデックス 0 から i までの最大の高さ、max_right[i] はインデックス i から n-1 までの最大の高さを表します。位置 i に溜まる水は max(0, min(max_left[i], max_right[i]) - height[i]) です。
max_left の構築には左から右への1回のパスが必要で、max_right の構築には右から左への1回のパスが必要です。最後のパスで水の量を合計します。この方法はコードが分かりやすく説明もしやすい一方、O(n) の追加領域を使います。
def trap_prefix(height):
n = len(height)
if n < 3:
return 0
max_left = [0] * n
max_right = [0] * n
max_left[0] = height[0]
for i in range(1, n):
max_left[i] = max(max_left[i-1], height[i])
max_right[-1] = height[-1]
for i in range(n-2, -1, -1):
max_right[i] = max(max_right[i+1], height[i])
water = 0
for i in range(n):
water += max(0, min(max_left[i], max_right[i]) - height[i])
return water
print(trap_prefix([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_prefix([4,2,0,3,2,5])) # 9アプローチ2：二つのポインタ（O(1) 空間）
二つのポインタを使うアプローチでは、時間計算量 O(n)、空間計算量 O(1) を実現できます。両端から left と right のポインタを開始します。それぞれの側からこれまでに確認した最大値として、max_left と max_right を維持します。
各ステップでは、これまでの最大値が小さい側を処理します。なぜなら、その側が水位を制限する要因になるからです。max_left < max_right の場合、left ポインタの位置に溜まる水は max_left - height[left] です（右側が十分に高いためです）。left ポインタを内側へ移動します。それ以外の場合は、対称的に right 側を処理します。事前計算配列は必要ありません。
def trap_two_pointer(height):
left, right = 0, len(height) - 1
max_left = max_right = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left] # new max on the left
else:
water += max_left - height[left] # trapped by max_left
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
print(trap_two_pointer([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_two_pointer([4,2,0,3,2,5])) # 9
print(trap_two_pointer([3,0,3])) # 3二つのポインタが機能する理由：不変条件
重要な着眼点は、height[left] < height[right] なので left ポインタを処理するとき、max_right >= height[right] > height[left] が分かることです。したがって、右側の実効的な水の境界は少なくとも height[right] であり、これはすでに max_left より大きくなっています。そのため、min(max_left, effective_max_right) = max_left となり、水の公式は max_left - height[left] に簡略化できます。
正確な max_right を知る必要はありません。それが少なくとも height[right] > height[left] であると分かれば、max_left を水位として使うには十分です。この洗練された不変条件によって、O(1) 空間が可能になります。
# Trace two-pointer on [4, 2, 0, 3, 2, 5]
height = [4, 2, 0, 3, 2, 5]
left, right = 0, len(height) - 1
max_l = max_r = water = 0
print('height:', height)
print(f'{'Step':5} {'L':3} {'R':3} {'maxL':5} {'maxR':5} {'water':6} {'total':6}')
step = 0
while left < right:
side = 'L' if height[left] < height[right] else 'R'
if side == 'L':
if height[left] >= max_l: max_l = height[left]
else:
w = max_l - height[left]; water += w
left += 1
else:
if height[right] >= max_r: max_r = height[right]
else:
w = max_r - height[right]; water += w
right -= 1
step += 1
print(f'{step:5} {left:3} {right:3} {max_l:5} {max_r:5} {water:6}')
print('Total trapped:', water)アプローチ3：単調スタック（水平レイヤー）
単調スタックのアプローチでは、隣り合う棒の間にできる水平レイヤーごとに水量を計算します。インデックスを格納した単調減少スタックを維持します。棒 i がスタックのトップ j より高い場合、谷が形成されます。このとき、底は height[j]、j を取り出した後の左側の壁は height[stack[-1]]、右側の壁は height[i] です。谷には min(left_wall, right_wall) - floor の高さまで水がたまり、幅は i - stack[-1] - 1 になります。
高い棒に遭遇した時点で、それぞれの「谷」を計算します。これにより、水を境界のある長方形状の区間ごとに処理できます。そのため、どの棒が水位の形成に寄与しているかも追跡する必要がある場合に便利です。
def trap_stack(height):
stack = [] # monotonic decreasing indices
water = 0
for i in range(len(height)):
while stack and height[stack[-1]] < height[i]:
bottom_idx = stack.pop() # the floor of the valley
if not stack:
break # no left wall, no water
left_idx = stack[-1]
floor = height[bottom_idx]
water_height = min(height[left_idx], height[i]) - floor
width = i - left_idx - 1
water += water_height * width
stack.append(i)
return water
print(trap_stack([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_stack([4,2,0,3,2,5])) # 9単調スタックをトレースする
スタックのアプローチを使って [0,1,0,2,1,0,1,3,...] をトレースしてみましょう。i=3 で棒3（h=2）に遭遇したとき、スタックのトップは i=2（h=0）なので、これを取り出します。左側の壁は i=1（h=1）、右側の壁の高さは h=2 です。水の高さは min(1,2)-0=1、幅は 3-1-1=1、面積は 1 です。続いて、スタックのトップ i=1（h=1）は 2 より小さくないため、処理を止めます。そして 3 をスタックに追加します。
スタック法は2ポインタ法より実装が複雑ですが、それぞれの水のセルを形成する具体的な棒を明らかにできます。この知見は、水の配置を復元したり、異なる谷の数を数えたりする追加問題で役立ちます。
def trap_stack_trace(height):
stack = []
water = 0
for i in range(len(height)):
print(f'i={i} h={height[i]}: stack={[height[s] for s in stack]}')
while stack and height[stack[-1]] < height[i]:
bot = stack.pop()
if not stack:
print(f' Pop {height[bot]}: no left wall, skip')
break
left = stack[-1]
h = min(height[left], height[i]) - height[bot]
w = i - left - 1
water += h * w
print(f' Pop {height[bot]}: floor={height[bot]}, left_wall={height[left]}, right_wall={height[i]}, h={h}, w={w}, +{h*w}')
stack.append(i)
return water
result = trap_stack_trace([0,1,0,2,1,0,1,3,2,1,2,1])
print('Total:', result)3つのアプローチを比較する
雨水をためる問題に対する3つのアプローチをまとめます。
- プレフィックス配列：時間計算量 O(n)、空間計算量 O(n) です。最も理解しやすく、正しさも確認しやすい方法です。空間効率よりも分かりやすさが重視される面接に適しています。
- 2ポインタ：時間計算量 O(n)、空間計算量 O(1) です。時間と空間の両方で最適です。「O(1)空間で実装できますか？」という追加質問に適しています。
- 単調スタック：時間計算量 O(n)、空間計算量 O(n) です。水を水平レイヤーごとに処理します。どの棒が水の形成に寄与しているかを知りたい場合や、この問題がより大きなスタックベースのアルゴリズムのサブ問題として登場する場合に適しています。
height = [0,1,0,2,1,0,1,3,2,1,2,1]
# All three methods — verify they agree
def trap_prefix(h):
n = len(h)
ml = [0]*n; mr = [0]*n; ml[0]=h[0]; mr[-1]=h[-1]
for i in range(1,n): ml[i]=max(ml[i-1],h[i])
for i in range(n-2,-1,-1): mr[i]=max(mr[i+1],h[i])
return sum(max(0,min(ml[i],mr[i])-h[i]) for i in range(n))
def trap_two_ptr(h):
l,r,ml,mr,w = 0,len(h)-1,0,0,0
while l<r:
if h[l]<h[r]:
ml=max(ml,h[l]); w+=ml-h[l]; l+=1
else:
mr=max(mr,h[r]); w+=mr-h[r]; r-=1
return w
def trap_stk(h):
stk,w = [],[]
for i in range(len(h)):
while stk and h[stk[-1]]<h[i]:
b=stk.pop()
if not stk: break
w.append(max(0,min(h[stk[-1]],h[i])-h[b])*(i-stk[-1]-1))
stk.append(i)
return sum(w)
for h in [height, [4,2,0,3,2,5], [3,0,3], [1,0,1]]:
p=trap_prefix(h); t=trap_two_ptr(h); s=trap_stk(h)
print(f'{h}: prefix={p}, two-ptr={t}, stack={s}, match={p==t==s}')最大の水量を入れられる容器
最大の水量を入れられる容器（LeetCode 11）は、雨水をためる問題とよく混同されます。こちらでは、棒をちょうど2本選び、その2本だけで水を囲みます（内部にある棒は考慮しません）。面積 min(height[l], height[r]) × (r - l) を最大化します。
2ポインタ法を貪欲に使って解けます。まず両端から始めます（幅が最大の状態です）。短い方のポインタを内側へ移動します。高い方を移動しても面積は小さくなるだけだからです。時間計算量は O(n)、空間計算量は O(1) であり、実行中の最大値を保持する必要がないため、雨水をためる問題の2ポインタ法よりも単純です。
def max_water_container(height):
left, right = 0, len(height) - 1
max_area = 0
while left < right:
area = min(height[left], height[right]) * (right - left)
max_area = max(max_area, area)
# Move the shorter bar: moving taller bar can only reduce min
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
print(max_water_container([1,8,6,2,5,4,8,3,7])) # 49: bars 8 and 7
print(max_water_container([1,1])) # 1
print(max_water_container([4,3,2,1,4])) # 16
# Key difference from trapping rain water:
# Container: choose 2 bars, water fills freely between them (no internal barriers)
# Trapping: water fills ALL valleys in the full elevation map発展：Trapping Rain Water II（3D）
Trapping Rain Water II（LeetCode 407）は、2次元の高さ行列へ拡張した問題です。水は4方向すべてに流れることができ、境界を越えて外へ流れ出ます。解法には最小ヒープを使います。まずすべての境界セルをヒープに追加し、その後、BFSのように探索を広げます。最も高さの低いセルから処理します。高さがそれより低い隣接セルには、少なくとも現在のセルと同じ高さまで水がたまるためです。
これは1次元の場合とは根本的に異なるアルゴリズムであり、ヒープ操作とBFS走査の両方が問われます。1次元の2ポインタのテクニックは2次元には一般化できませんが、ヒープによるアプローチは一般化できます。
import heapq
def trap_rain_water_2d(heightMap):
if not heightMap or not heightMap[0]:
return 0
m, n = len(heightMap), len(heightMap[0])
visited = [[False]*n for _ in range(m)]
heap = [] # (height, row, col)
# Add all border cells to the heap
for i in range(m):
for j in [0, n-1]:
heapq.heappush(heap, (heightMap[i][j], i, j))
visited[i][j] = True
for j in range(n):
for i in [0, m-1]:
if not visited[i][j]:
heapq.heappush(heap, (heightMap[i][j], i, j))
visited[i][j] = True
total = 0
max_h = 0
while heap:
h, r, c = heapq.heappop(heap)
max_h = max(max_h, h)
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r+dr, c+dc
if 0<=nr<m and 0<=nc<n and not visited[nr][nc]:
visited[nr][nc] = True
total += max(0, max_h - heightMap[nr][nc])
heapq.heappush(heap, (max(max_h, heightMap[nr][nc]), nr, nc))
return total
map2d = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
print(trap_rain_water_2d(map2d)) # 4面接で各手法を使う場面
雨水をためる問題の面接に向けた選択ガイドです。
- 最初に使う方法：プレフィックス配列 — 説明しやすく、直感的に理解でき、正しさも明確です
- 「O(1)空間でできますか？」という追加質問：2ポインタ — 短い側がボトルネックになるという不変条件を説明します
- 面接官から「別のアプローチはありますか？」と聞かれた場合：単調スタック — 水平レイヤーごとの計算を説明します
コードに入る前に、各位置の水位を決めるもの（左右それぞれにある最も高い棒の高さの最小値）を必ず明確に定義してください。これにより、問題を理解していることを示せるだけでなく、解法も説明しやすくなります。
# Quick summary of all three approaches
approaches = [
{
'name': 'Prefix max arrays',
'time': 'O(n)', 'space': 'O(n)',
'description': '3 passes: build max_left, max_right, sum water column-by-column',
},
{
'name': 'Two pointers',
'time': 'O(n)', 'space': 'O(1)',
'description': 'Process smaller side: its max is the limiting wall, no array needed',
},
{
'name': 'Monotonic stack',
'time': 'O(n)', 'space': 'O(n)',
'description': 'Compute water in horizontal layers when a taller bar is encountered',
},
]
for a in approaches:
print(f'{a["name"]} [{a["time"]} / {a["space"]}]')
print(f' {a["description"]}')
print()エッジケースとよくある間違い
雨水をためる問題でよくある間違いを紹介します。
- min を忘れる：水位は
min(max_left, max_right)であり、どちらか一方だけではありません。棒の両側に高い壁が必要です。 - 水量が負になる：ある位置の高さが水位を超える場合は、
max(0, ...)を使って負の値を0に切り詰めます。 - 端の位置を考慮しない：左端と右端の棒には、片側に壁がないため水は決してたまりません。プレフィックス配列のアプローチでは、
max_left[0] = height[0]によってインデックス0の水量が常に0になるため、自然に処理できます。 - 空または非常に小さい配列：要素数が3未満の配列に対しては0を返します。
def trap(height):
n = len(height)
if n < 3:
return 0 # need at least 3 bars to trap anything
left, right = 0, n - 1
max_l = max_r = water = 0
while left < right:
if height[left] <= height[right]:
if height[left] >= max_l:
max_l = height[left]
else:
water += max_l - height[left] # never negative: max_l > height[left]
left += 1
else:
if height[right] >= max_r:
max_r = height[right]
else:
water += max_r - height[right]
right -= 1
return water
# Edge cases
print(trap([])) # 0: empty
print(trap([1])) # 0: single bar
print(trap([1,2])) # 0: two bars
print(trap([3,0,3])) # 3: simple valley
print(trap([3,3,3])) # 0: flat top, no water理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、雨水をためる問題は、各位置で左右それぞれにある最も高い壁の高さの最小値を求めることで解けること、2ポインタによる O(1) 空間のアプローチは、短い側の実行中の最大値が常に制約条件になるため機能すること、そして単調スタックのアプローチは水を水平レイヤーごとに計算でき、他のスタックベースのロジックと組み合わせる場合に役立つことを学びました。次はシステム設計の概念に移り、構造化された面接回答のための RADIO フレームワークから始めます。
よくある質問
「Trapping Rain Water：スタックとTwo-Pointer」レッスンは無料ですか？
はい。「Trapping Rain Water：スタックとTwo-Pointer」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「Trapping Rain Water：スタックとTwo-Pointer」で何を学びますか？
水平な層を計算する単調スタック手法と、垂直な柱を計算するtwo-pointer手法の両方でtrapping-rain-waterを解きます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「Trapping Rain Water：スタックとTwo-Pointer」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 単調スタック：増加と減少
- ヒストグラム内の最大長方形
- 単調デックによるSliding Window Maximum
- Trapping Rain Water：スタックとTwo-Pointer