Trapping Rain Water
幅がそれぞれ1単位の棒が横一列に並んでいます。height[i]は棒iの高さです。雨水は棒の間のくぼみにたまります。棒の上に水が残るのは、その棒より高い棒が左側と右側の両方にある場合だけです。最初の棒より左や最後の棒より右では、水は流れ落ちます。この列にたまる水の総量を返してください。
関数
- heightinteger-array
- 左から右へ並ぶ各棒の高さ
- 戻り値integer
- 溜まった水の総量
制約
1 ≤ height.length ≤ 2 × 1040 ≤ height[i] ≤ 105- 各棒の幅は1単位で、水は最初の棒より手前や最後の棒より先にはたまりません。
例
- 入力
- height = [0, 3, 1, 0, 2, 5, 1, 2]
- 出力
- 7
- 説明
- 3と5の間のレベルは3です。1の上に2単位、0の上に3単位、2の上に1単位あります。後の1は5と2の間にあるので、1を保持します。これで7になります。
- 入力
- height = [4, 1, 3, 0, 5]
- 出力
- 8
- 説明
- 低い壁は4なので、水はレベル4までたまります。1の上に3単位、3の上に1単位、0の上に4単位で、合計8になります。5が関係する前に、4の上から水があふれます。
- 入力
- height = [1, 2, 4, 2, 1]
- 出力
- 0
- 説明
- 棒は4まで上がり、再び下がります。すべての棒は、その先にそれより高いものがない側を持つため、水は流れ落ち、答えは0です。
発展問題
棒が高さを表す2Dグリッドを形成し、水が4方向すべてに流れ出せるとします。その場合、閉じ込められた水の量をどのように数えますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
行全体のことは忘れて、1本の棒に注目しましょう。棒
iの上に水はどれだけ高くたまるでしょうか。その高さを決めるのはどの棒でしょうか？棒
iの上の水位は、2つの数値のうち小さい方です。1つは先頭からiまでの最も高い棒の高さ、もう1つはiから末尾までの最も高い棒の高さです。棒iにたまる水の量は、その水位から棒自体の高さを引いた値です。両方向からそれぞれ1回走査すれば、左右の累積最大値を求められます。2 つの最大値のうち、小さい方だけが必要です。両端にポインターを 1 つずつ置き、それぞれのポインターが通過した最も高い棒を記録しておきます。低い棒の位置にあるポインターは、その位置の水位が自身のこれまでの最大値で決まるため、その分の水を加えて、そのポインターを内側へ移動します。ポインターが出会ったら停止します。
解説
ある棒の上にたまる水の量は、左右両側の遠くにある棒にも左右されます。その水位は、左側で最も高い棒と右側で最も高い棒のうち、低い方の高さです。そして、その棒の上にたまる水の量は、その水位から棒自体の高さを引いた値です。各手法の違いは、この2つの最大値の求め方だけです。
各バーの両側をスキャンする
正しいが、最大のテストでは終わらない
考え方
各バー i について、左側で最も高いバーを見つけるために 0 から i まで走査し、右側で最も高いバーを見つけるために i から末尾まで走査してから、min(leftMax, rightMax) - height[i] を加算します。どちらの走査にもバー i を含めることで、量が負にならず、端のバーの値が 0 になります。
各バーで行全体を読み取ります。n = 2 × 10^4 の場合、読み取り回数は 4 × 10^8 となり、その大半は直前のバーの走査を繰り返すものです。
アルゴリズム
waterを0に設定します。- 各インデックス
iについて、leftMaxを求めるために0からiまで走査します。 rightMaxを求めるためにiから最後のインデックスまで走査します。min(leftMax, rightMax) - height[i]をwaterに加算します。waterを返します。
def trap(height):
n = len(height)
water = 0
for i in range(n):
# The tallest bar at or left of i, and the tallest at or right of i.
left_max = 0
for j in range(i + 1):
left_max = max(left_max, height[j])
right_max = 0
for j in range(i, n):
right_max = max(right_max, height[j])
water += min(left_max, right_max) - height[i]
return water左右それぞれで最も高い棒を事前に計算する
考え方
0 から i までの最も高い棒は、0 から i-1 までの最も高い棒と height[i] のうち大きい方です。したがって、左から1回走査して、各要素をその直前の要素から構築しながら leftMax を埋め、右から1回走査して rightMax を埋めます。3回目の走査で公式を適用します。
[0, 3, 1, 0, 2, 5, 1, 2] の場合、各位置の水位 min(leftMax[i], rightMax[i]) は [0, 3, 3, 3, 3, 5, 2, 2] です。そこから高さを引くと [0, 0, 2, 3, 1, 0, 1, 0] となり、合計は7です。時間計算量は O(n) で、その代わりに n 個の数値を格納する配列を2つ使います。
アルゴリズム
leftMaxを左から右へ埋めます。leftMax[0] = height[0]とし、次にleftMax[i] = max(leftMax[i-1], height[i])とします。rightMaxを右から左へ埋めます。rightMax[n-1] = height[n-1]とし、次にrightMax[i] = max(rightMax[i+1], height[i])とします。- すべてのインデックスについて、
min(leftMax[i], rightMax[i]) - height[i]を合計に加えます。 - 合計を返します。
def trap(height):
n = len(height)
left_max = [0] * n # tallest bar from index 0 to i
right_max = [0] * n # tallest bar from index i to n-1
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i - 1], height[i])
right_max[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
right_max[i] = max(right_max[i + 1], height[i])
water = 0
for i in range(n):
water += min(left_max[i], right_max[i]) - height[i]
return water低い側を移動する2つのポインター
考え方
水量の計算に必要なのは低い方の壁だけであり、2つのポインターを使えばどちらが低いかを判定できます。leftを0、rightを最後のインデックスに設定し、各ポインターが自分自身も含めて通過した最も高い棒であるleftMaxとrightMaxを記録し、常に低い棒の側のポインターを動かします。すると、すでに通過した棒はすべて、現在の2本の棒のうち高い方よりも高くありませんheight[left] < height[right]だとします。不変条件より、leftMaxはleftの右側にある棒height[right]以下です。したがって、leftの右側の壁の高さは少なくともleftMaxであり、ポインターの間に何があっても、水面の高さはちょうどleftMaxになります。右側の棒の方が低いか同じ高さの場合も、対称的な議論でrightが確定します。
アルゴリズム
left = 0、right = n-1を設定し、leftMax、rightMax、waterを0に設定します。left < rightの間、height[left] < height[right]の場合は、必要に応じてleftMaxをheight[left]まで引き上げ、leftMax - height[left]を加算して、leftを右に進めます。- そうでなければ、右側で同じ処理を行い、
rightを左に進めます。 waterを返します。ポインターが合流する位置の棒が最も高く、水は溜まりません。
def trap(height):
left, right = 0, len(height) - 1
left_max = right_max = 0 # tallest bar passed so far from each end
water = 0
while left < right:
if height[left] < height[right]:
# A bar taller than height[left] waits on the right, so left_max sets the level here.
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
# A bar at least as tall as height[right] waits on the left, so right_max sets the level.
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return water
落とし穴と境界ケース
- 走査中の最大値を更新する前に水量を加算すること。
height[left]がleftMaxを上回ると、水量が負になり、合計が減少します。 - 高さの高い方の棒の側にポインターを動かすこと。その側の水位は確定していません。
[4, 1, 3, 0, 5]では、この方法だと答えは 8 ではなく 4 になります。 - 隣り合う棒だけを見ること。
[3, 0, 2, 0, 1, 0, 4]では、高さ 1 の棒の水位は 3 まで上がります。この水位は、4 本先と 2 本先の棒によって決まります。答えは 12 です。 - 配列の両端を壁として扱うこと。水は端から流れ出るため、棒が 1 本、2 本の場合や、単調に上がる、または単調に下がるだけの並びでは、水は 0 になります。
よくある質問3
Trapping Rain Water の時間計算量はどれくらいですか？
2ポインター法の解法は、各ステップでポインターを1つ内側に移動するため、時間計算量はO(n)、追加の空間計算量はO(1)です。leftMax配列とrightMax配列を使う方法も時間計算量はO(n)ですが、空間計算量はO(n)です。各バーから両側を走査すると、O(n²)になります。
スタックを使って「Trapping Rain Water」を解けますか？
はい。高さが低くなっていくインデックスをスタックに保持します。より高い棒が現れたら、スタックの一番上を取り出します。それが、新しいスタックの一番上と現在の棒に囲まれた水たまりの底になります。(min(two walls) - floor) × (distance between the walls - 1)を加算し、取り出し続けます。これにより、水を水平な層ごとに満たしていき、時間計算量と空間計算量はO(n)になります。
Trapping Rain WaterはContainer With Most Waterとどう違いますか？
「Container With Most Water」では、線は幅を持たず、答えは2本の線の間にある最大の長方形1つです。ここでは各棒が実体を持ち、答えはすべての棒にわたる水の合計です。どちらも同じ理由で低い側を動かします。その側の結果はすでに決まっているからです。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def trap(height):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
height = [0, 3, 1, 0, 2, 5, 1, 2]
期待される出力
7