Two Pointer Approach の原理
核心概念:
各位置で水がトラップできる量は、その位置の左側と右側の最大高度の最小値から現在の高度を引いた値です。
🔍 処理の流れ
- 初期化: 左右のポインタを配列の両端に設置
- 比較: 左右の高度を比較し、低い方を処理対象とする
- 更新: 最大高度を更新するか、水量を計算して加算
- 移動: 処理したポインタを中央に向かって移動
- 終了: 左右のポインタが交差するまで繰り返し
💡 なぜこの方法が正しいのか？
低い方の最大高度を基準にすることで、確実に水がトラップできる量を計算できます。高い方の側には必ずそれ以上の高度があることが保証されているため、低い方の制約が決定的になります。