ツーポインタで並んだ壁のあいだにたまる雨水の量を求める

幅 1 の壁の高さの並びから、雨が降ったあと壁のあいだにたまる水の量を求めます。両端から 2 本の指を寄せ、低い側の水の高さはもう決まっていると見抜く、ツーポインタの練習です。

海外で定番の問題リスト 4 本には入っていません

問題

庭に、幅 1 の壁が横に隙間なく並んでいます。左から順の壁の高さを、0 以上の整数の並び heights で受け取ります。雨が降ったあと、壁のあいだにたまる水の量 (幅 1、高さ 1 を 1 と数えた合計) を返す関数を書いてください。

左端より左と、右端より右には壁が無く、水はそこから流れ出ます
高さ 0 の所は地面で、水がたまれば地面の上にたまります
heights の長さは 0 以上 20000 以下で、値は 0 以上 100000 以下です

入力と出力の例

例 1

左の高さ 3 と右の高さ 4 の壁にはさまれ、水は高さ 3 までたまります。3 つの所に、3、1、3 の水がたまり、合計 7 です。

heights = [3, 0, 2, 0, 4]

例 2

まん中がいちばん高い山の形です。どこも片側が低く、水は流れ出るので、たまりません。

heights = [1, 2, 3, 2, 1]

例 3

左の 4 より右の 3 が低いので、水は高さ 3 までです。左から 2、2、3、1 の水がたまり、合計 8 です。

heights = [4, 1, 1, 0, 2, 3]

面接での聞かれ方

面接では、棒グラフの絵を見せて聞かれることがよくあります。

「この棒のあいだに、雨水はどれだけたまりますか？」
「O(n) の時間で、記憶を O(1) にできますか？」と、段を踏んで詰められます
「両端より外に水は流れますか？」と、決まりを自分から確かめるかも見られます

難しい問いとして知られていますが、1 つの所にたまる水の高さを先に式にすると、あとは計算の順を工夫するだけになります。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

1 つの所 i にたまる水を考えます。水の高さは、i より左 (i を含む) のいちばん高い壁と、右 (i を含む) のいちばん高い壁の、低い方で決まります。たまる量は、その高さから i の壁の高さを引いた値です。例 1 の左から 2 番目なら、左の最大 3、右の最大 4 の低い方 3 から 0 を引いて 3 です。

段 2

素直に書くなら、所ごとに左右をなめて最大を探します。正しく動きますが、1 つの所に O(n) かかるので全体で O(n²) です。左からの最大と右からの最大を前もって 2 本の並びに作っておけば O(n) になりますが、記憶を O(n) 使います。

段 3

両端に指を置き、左の最大と右の最大を持ちながら寄せていきます。左の壁が右の壁より低いなら、左の指の所の水の高さは、左の最大で決まります。右側には、いまの右の壁という、それ以上に高い壁がもうあると分かっているからです。そこで左の所の水を足して、左の指を進めます。右の方が低いか同じなら、逆に右の所を決めて右の指を戻します。

段 4

左の最大は、水を足す前に、いまの壁の高さで更新します。こうすると、いまの壁が最大を越えたときは足す量が 0 になり、負の水を足さずに済みます。

解答

Python

def trapped_water(heights):
    lo = 0
    hi = len(heights) - 1
    lmax = 0
    rmax = 0
    water = 0
    while lo < hi:
        a = heights[lo]
        b = heights[hi]
        if a < b:
            lmax = max(lmax, a)
            water += lmax - a
            lo += 1
        else:
            rmax = max(rmax, b)
            water += rmax - b
            hi -= 1
    return water

JavaScript

function trappedWater(
  heights
) {
  let lo = 0;
  let hi = heights.length - 1;
  let lmax = 0;
  let rmax = 0;
  let water = 0;
  while (lo < hi) {
    const a = heights[lo];
    const b = heights[hi];
    if (a < b) {
      lmax = Math.max(lmax, a);
      water += lmax - a;
      lo++;
    } else {
      rmax = Math.max(rmax, b);
      water += rmax - b;
      hi--;
    }
  }
  return water;
}

Go

func trappedWater(
	heights []int,
) int {
	lo, hi := 0, len(heights)-1
	lmax, rmax := 0, 0
	water := 0
	for lo < hi {
		a := heights[lo]
		b := heights[hi]
		if a < b {
			lmax = max(lmax, a)
			water += lmax - a
			lo++
		} else {
			rmax = max(rmax, b)
			water += rmax - b
			hi--
		}
	}
	return water
}

lo と hi が左と右の指、lmax と rmax がそれぞれの側でここまでに見た最大の高さです。低い側の所だけを決めて、その指を内へ動かします。空の並びでは hi が -1 から始まり、繰り返しに入らずに 0 を返します。

計算量

時間は O(n) です。2 本の指は合わせて n - 1 回動き、1 回の手間は一定です
使う記憶は O(1) です。指 2 本と最大 2 つと合計だけを持ちます
段 2 の所ごとに左右をなめる書き方は O(n²)、左右の最大を並びに作る書き方は時間 O(n) で記憶 O(n) です

よくある間違い

水の高さを、左右の最大の高い方で決める。低い方の壁の上から水はこぼれます。例 3 で高い方の 4 を使うと、右端の 3 より高く水を積んで、8 より多く返します
最大を更新する前に水を足す。いまの壁が最大より高いとき、lmax - a が負になり、水を減らしてしまいます。最大を先に更新します
大きい方の指を動かす。低い側の所は水の高さが決まっていますが、高い側の所はまだ決まっていません。動かすのは低い側です
両端の所にも水を足そうとする。端の外に壁は無いので、端の所に水はたまりません。左右の最大を端の壁から始めれば、自然に 0 になります

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def trapped_water(heights: list[int]) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(trapped_water([3, 0, 2, 0, 4]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します