雨水をためる（LeetCode #42）

高さの異なる柱の間に残る水量を求めます。各列の水位は、左右で最も高い境界のうち低い方で決まります。どの時点で境界が確定するかを示し、各列の非負の深さを足します。

雨水計算の仕組み

left_max[i] は先頭から i まで、right_max[i] は i から末尾までの最高柱です。列 i の水深は次です。

min(left_max[i], right_max[i]) - height[i]

両最大値に現在の柱も含めるので非負です。一方の壁だけが高くても、水は低い側から流れます。

前後の最大値法は二配列を作り、各列に式を適用します。時間 O(n)、追加空間 O(n)。二ポインター法は left、right、left_max、right_max だけを保持します。

小さい境界側を確定できる理由

各段階で現在の端点を含む最大値を更新します。left_max <= right_max なら、右には左以上の壁をすでに見ています。未知の柱は右の最大値を上げられても、既知の壁を消せません。水は左の境界も超えられないので、左の現在列は left_max - height[left] で確定します。

左列を記録して内側へ進みます。right_max < left_max なら対称に右を確定します。毎回一列が最終値となり、再訪は不要です。

計算をステップで追う

既定は height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]、二ポインター法です。

1. 列 0 と 11 の最大値は 0 と 1。左列を深さ 0 で確定。
2. 列 1、2 も左から確定し、列 2 は 1 - 0 = 1。
3. 列 3 で left_max は 2、right_max はまだ 1。右列 11 を深さ 0 で確定。
4. 列 10 で right_max が 2。等しい時は左を選び、列 3、4、5、6 が 0、1、2、1 を加え、合計 5。
5. 列 7 で left_max が 3。右が小さくなり、列 10、9、8 が 0、1、0 を加える。
6. 列 7 だけ残る。両端の更新済み最大値が同じなので左分岐で深さ 0。合計 6。

前後の最大値法に切り替えると、左配列は [0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]、右配列は [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1]。深さは [0, 0, 1, 0, 1, 2, 1, 0, 0, 1, 0, 0] で、同じ 6 になります。

時間・空間計算量

どちらのアニメーションも列あたり定数の作業です。前後最大値は 3 回の線形走査、二ポインタは確定する列ごとに定数の作業をします。入力の 14 本上限は表示の制約です。

境界を比べ、小さい境界に制限される側を動かす証明は Container With Most Water にも現れます。ただしそちらは現在の端点の高さで、走査中の最大値ではありません。前後の最大値は、後の多数の問い合わせで各方向の最良境界が必要な時にも使えます。

境界ケース

• 三本未満では水を囲めない。
• 空、平坦、単調な斜面は 0。
• 最大値が同じなら、この実装は左を確定する。
• 高さ 0 は欠損ではなく通常の列。深い窪みなら一列に複数単位たまる。
• 最初と最後は片側の外壁がなく、水深 0。

よくある間違い

• min の代わりに max。 低い壁を超える架空の水を数えます。
• 二つの不変条件を混ぜる。 端点だけを比較し、未更新の走査最大値で計算しないでください。
• 記録より先にポインターを動かす。 列を飛ばすか、別の添字に水を計上します。
• 減算前に最大値を更新しない。 負の深さを作る恐れがあります。
• 同値で停止する。 一貫した同点規則で進めば十分です。