雨水を溜める

谷を数えようとすると、どこまでが 1 つの谷か決まらない

[0,1,0,2,1,0,1,3,2,1,2,1] に雨を降らせると 6 溜まります。この 6 をどう数えるかを考えるとき、多くの人はまず「谷を見つけて、その谷の面積を出す」方向へ進みます。

ところが谷は入れ子になります。小さなくぼみの上に、もっと大きなくぼみがかぶさっている。どこからどこまでを 1 つの谷と呼ぶかが決まらず、境目の扱いで場合分けが増えていきます。面のまま数えようとした時点で、この問題は難しくなります。

縦に 1 マスずつ数える

見方を変えて、位置 i の真上に水が何段積まれるかだけを考えます。すると、その 1 マスの水位を決めているのは 3 つの値だけになります。自分の高さと、自分より左にある壁のいちばん高いところと、自分より右にある壁のいちばん高いところです。

バケツと同じで、低いほうの壁を越えた水はこぼれます。だから水面の高さは、左右の高いほうではなく低いほうで決まります。そこから自分の高さを引いた分が、その位置に溜まる量です。全部の位置で足せば答えになります。

谷の境目という話が消えて、各位置を独立に計算できる形になりました。残るのは、左右の最大値をどう用意するかだけです。

「そこまでの最大」は、1 回なめれば作れる

位置ごとに毎回左側を全部見直すと O(n^2) に戻ってしまいます。しかし左側の最大値は、1 つ手前の結果から一手で作れます。

同じ要領で右端からも 1 回なめれば、両側の最大値が揃います。配列を 2 本ぶん持つのでメモリは O(n) 使いますが、時間は O(n) に収まります。

メモリまで削りたい場合は、両端から 2 つの位置を寄せていく書き方があります。低いほうの側だけは先に確定させてよい、という性質を使う手ですが、飲み込みにくいので、まずは配列を用意する形で確実に動かしてからで構いません。

境目の扱いも先に決めておきます。左側の最大値に自分自身を含めるかどうかで、答えが変わります。含めておくと、自分が周りより高いときに水位と高さが同じになり、溜まる量が素直に 0 になります。含めないと負の値が出るので、後から 0 に丸める処理が要ります。どちらでも正解には辿り着けますが、丸め忘れると [5,5,5,5] のような入力で合計がずれます。

そして空の配列です。長さ 0 で先頭の要素を読もうとすると落ちるので、いちばん最初に片付けておいてください。

やってみよう

trapWater(height) を実装してください。height は 0 以上の整数の配列で、溜まる水の合計を整数で返します。空配列のときは 0 を返してください。計算量は O(n) にします。

1. 関数 trapWater(height) を実装し、溜まる水量の合計を整数で返す
2. 計算量は O(n) であること (leftMax / rightMax 配列方式または 双方向ポインタ 方式)
3. 空配列 のときは 0 を返す