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の間にあるので、水位は2で、1単位の水がたまります。2 + 3 + 1 + 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です。
提出時に隠しテスト+17件
発展問題
棒が高さを表す2Dグリッドを形成し、水が4方向すべてに流れ出る可能性があるとします。その場合、たまった水の量をどのように数えますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
行全体のことは忘れて、1本の棒を見てみましょう。棒
iの上に水はどれだけ高くたまるでしょうか。また、その高さを決めるのはどの棒でしょうか？棒
iの上の水位は、2つの数値のうち小さい方です。1つは先頭からiまでの最も高い棒の高さ、もう1つはiから末尾までの最も高い棒の高さです。棒iにたまる水の量は、その水位から棒自体の高さを引いた値です。両方向からそれぞれ1回走査すれば、両方の累積最大値を求められます。2つの最大値のうち、小さい方だけが必要です。両端にポインターを1つずつ置き、それぞれのポインターが通過した最も高い棒を記録しておきます。低い棒の上にあるポインターの水位は、そのポインターの現在までの最大値で確定します。その分の水を加え、そのポインターを内側へ動かします。ポインターが合流したら終了です。
解説
各柱の上にたまる水の量は、左右のかなり離れた位置にある柱にも左右されるため、隣の柱だけを見ると誤った結果になります。解決策は1つの式です。ある柱の上の水位は、その柱の左側で最も高い柱と右側で最も高い柱のうち、低い方です。各柱について左右の最大値を走査して求める方法は遅く、2つの配列に保存すれば線形時間で処理でき、低い側を常に動かす2つのポインターを使えば配列は不要です。
各バーの両側をスキャンする
正しいが、最大のテストでは終わらない
考え方
水の量を棒ごとに数えます。インデックス i の棒の上の水は、左右の壁のうち低い方からあふれる高さまでたまります。左の壁は、インデックス 0 から i までの範囲で最も高い棒です。右の壁は、i から末尾までの範囲で最も高い棒です。したがって水面の高さは min(leftMax, rightMax) で、棒 i の上にある水の量は、その高さから height[i] を引いた値です。
[0, 3, 1, 0, 2, 5, 1, 2] を考え、インデックス 3 にある 0 の棒を見てみましょう。左側で最も高い棒は 3、右側では 5 です。水面の高さは 3 なので、そこには 3 単位の水がたまります。インデックス 6 にある 1 の棒の場合、壁の高さは 5 と 2 です。水面の高さは 2 で、1 単位の水がたまります。
どちらの走査にも棒 i 自体が含まれます。これにより答えが負にならないようにしています。棒 i が片側のどの棒よりも高い場合、その側の最大値は棒自体の高さとなり、水面の高さはその棒の高さと等しくなるため、水は 0 になります。最初と最後の棒には常に水が 0 になるのも、このためです。
問題は計算コストです。棒ごとに列全体を調べ、左半分と右半分を走査するため、合計の読み取り回数は n × n になります。棒が 2 × 10^4 本の場合、4 × 10^8 回です。また、走査では同じ処理を繰り返しています。インデックス 5 の左側で最も高い棒は、インデックス 4 の左側で最も高い棒に比較を 1 回追加すれば求められますが、ブルートフォースでは毎回ゼロから再計算します。
アルゴリズム
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回目の走査では、各棒について min(leftMax[i], rightMax[i]) - height[i] を加算します。
[0, 3, 1, 0, 2, 5, 1, 2] の場合、leftMax = [0, 3, 3, 3, 3, 5, 5, 5]、rightMax = [5, 5, 5, 5, 5, 5, 2, 2] です。それぞれの小さい方の値が、水位 [0, 3, 3, 3, 3, 5, 2, 2] になります。高さを引くと [0, 0, 2, 3, 1, 0, 1, 0] となり、合計は7です。
各走査ではすべての棒を1回ずつ調べるので、時間計算量は O(n) です。棒が2 × 10^4本なら、4 × 10^8ステップではなく約6 × 10^4ステップで済みます。その代わり、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つの壁のうち低い方だけです。あるインデックスで左の壁の方が低いと証明できれば、そのインデックスの右の壁はもう必要ありません。2つのポインターを使えば、それを証明できます。leftをインデックス0に、rightを最後のインデックスに置き、それぞれのポインターがこれまでに通過したバーのうち最も高いもの（ポインターが現在指しているバーも含む）であるleftMaxとrightMaxを保持します。
不変条件は次のとおりです。ポインターがすでに通過したすべてのバーは、現在ポインターが指している2つのバーのうち高い方よりも高くありません。低い方のバーにあるポインターを常に動かすため、この条件は成り立ちます。つまり、ポインターはもう一方のポインターの下にあるバーより高くないバーだけを通過します。
ここで、height[left] < height[right]だとします。不変条件より、leftMaxはheight[right]以下であり、height[right]はそれ自体がleftの右側にあるバーです。したがって、leftの真の右側の壁は少なくともleftMaxと同じ高さであり、ポインターの間に何があろうと、leftの水位はちょうどleftMaxです。leftMax - height[left]を加算し、leftを右に1つ進めます。height[right]が低い方、または同じ高さの場合は、右側で左右を反転した処理を行います。水量を加算する前に現在までの最大値を更新します。これにより、ポインターの下にあるバー自体が壁として数えられ、水量が負になることはありません。
[0, 3, 1, 0, 2, 5, 1, 2]を順に見ていきましょう。ポインターは0と2から始まります。左の方が低く、水量は0です。次は3と2で、右の方が低く、rightMaxは2になり、水量は0です。次は3と1で、再び右の方が低く、1の位置には2-1 = 1の水がたまります。次に3と5では左の方が低くなります。leftMaxは3で、3の位置の水量は0、1の位置は2、0の位置は3、2の位置は1です。ポインターは5の位置で合流します。合計は1 + 2 + 3 + 1 = 7です。1回の走査と4つの変数で求められます。
アルゴリズム
left = 0、right = n-1を設定し、leftMax、rightMax、waterを0に設定します。left < rightの間、height[left]とheight[right]を比較します。- 左側の棒が低い場合、必要に応じて
leftMaxをheight[left]に更新し、leftMax - height[left]を加算して、leftを右に移動します。 - そうでない場合、必要に応じて
rightMaxをheight[right]に更新し、rightMax - height[right]を加算して、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
落とし穴と境界ケース
式は短く、誤答の多くは2行の順序や、どちら側に移動するかによって生じます。
- 現在の最大値を更新する前に水を加えること。
height[left]がleftMaxより高い場合、leftMax - height[left]は負になり、合計が減ってしまいます。まず最大値を更新してから、加算してください。 - 高い方の棒にあるポインターを動かすこと。水位がわかるのは低い方だけです。高い方を動かすと、まだ根拠を確認していない壁を使うことになります。
[4, 1, 3, 0, 5]では、この方法だと答えは8ではなく4になります。 - 最も近い隣の棒だけを見ること。ある棒の壁は遠くにあることがあります。
[3, 0, 2, 0, 1, 0, 4]では、1の棒には、水位3まで水がたまります。この水位は、4つ先と2つ先の棒によって決まります。この場合の答えは12です。 - 配列の両端を壁として扱うこと。最初または最後の棒を越えた水は流れ落ちるため、棒が1本だけの場合、2本だけの場合、または一方向にしか上がらない、あるいは下がらない並びでは、水は0です。
- ブルートフォースで棒
i自身を探索対象から除外すること。その場合、両側より高い棒では水量が負になります。棒自身を含めるか、結果を0で下限処理してください。 - 乗算を行う変形版ではオーバーフローに注意してください。ここで答えは約2 × 10^9（10^5の高さの棒2本の間に、何もないセルが19,998個ある場合）に達しますが、符号付き32ビット整数には収まります。独自の変形版では、合計に64ビット整数を使ってください。
よくある質問4
Trapping Rain Water の時間計算量は何ですか？
2 つのポインターを使う解法は、時間計算量が O(n)、追加の空間計算量が O(1) です。各ステップで一方のポインターを内側に動かすため、ステップ数は n-1 です。leftMax 配列と rightMax 配列を使う方法も時間計算量は O(n) ですが、空間計算量は O(n) です。各棒から両側をスキャンすると O(n²) となり、棒が 2 × 10^4 本の場合、読み取り回数は約 4 × 10^8 回です。
なぜ2ポインター解法では、短い方の辺を動かすのでしょうか？
すでに通過したすべての棒の高さは、現在の2本の棒のうち高い方を超えません。動くのは低い方のポインターだけだからです。したがって、左の棒の方が低いとき、その時点までの最大値は右の棒以下であり、右側には実際の壁があります。ポインター間に何があろうと、左ポインターの位置の水位はその時点までの最大値なので、その棒の処理を確定して先に進めます。
スタックを使って「Trapping Rain Water」を解くことはできますか？
はい。高さが下から上へと低くなるインデックスをスタックに保持します。スタックの頂上より高い棒が来たら、頂上を取り出します。その棒は、スタックの新しい頂上と現在の棒を両側の壁とする水たまりの底になります。(min(two walls) - floor) × (distance between the walls - 1)を加算し、現在の棒が高い間は取り出し続けます。このスタックを使うと、列ではなく横方向の層ごとに水を満たし、O(n)時間、O(n)領域で処理できます。
Trapping Rain Water は Container With Most Water とどう違いますか？
「Container With Most Water」では、2本の線を選び、その間の線は領域を占めないため、答えは最大の長方形1つです。ここでは各棒が塊になっていて、それぞれの棒の上に水が溜まり、答えはすべての棒についての合計です。どちらも同じ理由で、低い側を動かす2ポインターを使います。低い側は、その結果がすでに決まっている側だからです。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def trap(height):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
height = [0, 3, 1, 0, 2, 5, 1, 2]
期待値
7