雨水を溜める
雨水を溜める
このレッスンで分かること
- 「左の壁」「右の壁」「自分の高さ」の
3 つの値の関係で水位が決まる、というのが Trapping Rain Water の核心- これは
LeetCode Hardの常連であり、配列+双方向ポインタのテクニックを最大限に活かせる名作問題ですheight = [0,1,0,2,1,0,1,3,2,1,2,1]のとき、答えは6です
雨水を溜める とは
棒グラフ状の
高さ配列で溜まる雨水量を求める。左右の最大値配列を使うO(n)解とO(1)の双方向ポインタ解を学ぶ。
これは LeetCode Hard の常連であり、配列 + 双方向ポインタ のテクニックを最大限に活かせる名作問題です。整数配列 height が 棒グラフ の高さを表すとき、雨が降ったらこの地形にどれだけ 水 が溜まるかを求めます。本レッスンでは段階的に O(n^2) → O(n) → O(1) 追加メモリ まで最適化します。
各位置に溜まる水は、その位置の
左側の最大高さと右側の最大高さのうち小さい方から、自分の高さを引いた値だ。
直感をつかむ
height = [0,1,0,2,1,0,1,3,2,1,2,1] のとき、答えは 6 です。各 バー の上に水が溜まる量を可視化すると、バーが谷になっている部分 に水が貯まります。あるバーの上の水の高さは、左右の最も高い壁のうち低い方で決まります。
解法 1: 左右の最大値配列 (O(n) 時間 / O(n) 空間)
leftMax[i] を height[0..i] の最大、rightMax[i] を height[i..n-1] の最大として 2 本の配列を事前計算します。あとは min(leftMax[i], rightMax[i]) - height[i] を全位置で合計するだけ。
Python
def trapWater(height):
n = len(height)
if n == 0:
return 0
leftMax = [0] * n
rightMax = [0] * n
leftMax[0] = height[0]
for i in range(1, n):
leftMax[i] = max(leftMax[i - 1], height[i])
rightMax[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
rightMax[i] = max(rightMax[i + 1], height[i])
total = 0
for i in range(n):
total += min(leftMax[i], rightMax[i]) - height[i]
return totalシンプルで分かりやすく、これだけでも O(n) で動きます。本問題はまずこの解を確実に書けることが目標です。
解法 2: 双方向ポインタ (O(n) 時間 / O(1) 空間)
左右から 2 本のポインタ で挟み込み、小さい方 のポインタを進めながら その時点の最大値との差 を加算していきます。leftMax / rightMax 配列を作らずに済むので 空間 が O(1) になります。
JavaScript
function trapWater(height) {
let l = 0, r = height.length - 1;
let leftMax = 0, rightMax = 0;
let total = 0;
while (l < r) {
if (height[l] < height[r]) {
if (height[l] >= leftMax) leftMax = height[l];
else total += leftMax - height[l];
l++;
} else {
if (height[r] >= rightMax) rightMax = height[r];
else total += rightMax - height[r];
r--;
}
}
return total;
}双方向ポインタ解は最初は呑み込みにくい。まずは
O(n) 空間版を完全に書けるようにしてから、空間最適化の理由を後追いするのが近道。
なぜ min を使うか
左右いずれかの壁が低いと、水はその低い壁の高さまでしか溜まりません。バケツの理屈と同じです。min(leftMax, rightMax) < height[i] のときは溜まらない (= 自分が壁になっている) ので、max(0, ...) で安全側に倒します。今回の test_cases では負にならないので、min - height[i] だけで十分です。
「左の壁」「右の壁」「自分の高さ」の
3 つの値の関係で水位が決まる、というのが Trapping Rain Water の核心。
よくある間違い
leftMax[i]をheight[0..i-1]の最大 (自分を含まない) と勘違いする。含むのが正解。空配列を受け取った時のIndexError。最初にif n == 0: return 0を必ず入れる。- 双方向ポインタ版で
小さい方のポインタを進めるルールを忘れる。両側からどちらを進めるかが本質。
やってみよう
trapWater(height) を実装してください。整数配列 height (各値は 0 以上) を受け取り、溜まる雨水量 の合計を整数で返します。空配列 のときは 0 を返します。O(n) で実装してください (空間は O(n) でも O(1) でも OK)。
よくある質問
Q. このトピックは実務でどう役立ちますか？
A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。
Q. 計算量はどう求めれば良いですか？
A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。
Q. 覚えるべき定番アルゴリズムは何ですか？
A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。
次のレッスン
次は 最終総まとめクイズ で、これまで学んだアルゴリズムの総復習をします。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 雨水を溜める の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 雨水を溜める とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 関数
trapWater(height)を実装し、溜まる水量の合計を整数で返す - 計算量は
O(n)であること (leftMax/rightMax配列方式または双方向ポインタ方式) 空配列のときは0を返す
入出力例
test-cases.txt
trapWater([0,1,0,2,1,0,1,3,2,1,2,1]) → 6
trapWater([4,2,0,3,2,5]) → 9
trapWater([0,1,2,1,0]) → 0
trapWater([3,0,3]) → 3
trapWater([5,5,5,5]) → 0
trapWater([1,2,3,4]) → 0
trapWater([4,3,2,1]) → 0