問題と適用シナリオ
長さ n の非負整数配列 height が与えられます。height[i] はインデックス i の棒の高さを表し、すべての棒の幅は 1 です。これらの棒によって溜まる雨水の総量を計算してください。例：
height = [4, 2, 0, 3, 2, 5]
result = 9目標は O(n) 時間および O(1) 補助空間です。標準的な制約は 1 <= n <= 20000 および 0 <= height[i] <= 100000 です。高さが負になることはなく、元の問題では各棒の上の個別の貯水量を求めることは要求されていません。
この質問には公開された直接の面接実績があります。2025年6月の百度（Baidu）のGoバックエンドインターン面接の体験記では、「Trapping Rain Water」が3つのライブコーディング課題の1つとして挙げられています。また、別の公開電話面談レポートでは、特定の位置に有限量の水を注ぐバリアントが出題されています。英語および中国語のLeetCode問題ページではHardに分類され、配列、2ポインタ、動的計画法、スタック、単調スタックのタグが付いています。核となるスキルは局所的な計算式から線形アルゴリズムを導出して証明することであるため、実装言語や職種に関係なくカテゴリは coding です。
面接官が見ているポイント
第1に、1本の棒の上の正確な水量を表現できるかです。インデックス i の水位は、左右に隣接する2つの棒ではなく、その左側にある最も高い棒と右側にある最も高い棒の「低い方」によって制限されます。leftMax[i] と rightMax[i] の両方がインデックス i を含む場合、その水量は min(leftMax[i], rightMax[i]) - height[i] です。
第2に、プレフィックス配列とサフィックス配列を定数空間に圧縮できるかです。すべての左右の最大値を保存すると、簡単な O(n) 時間の解法が得られます。2ポインタ法は、既知の境界が小さい方を見るだけで片側の1列を確定できるという、より強力な観察を利用します。
第3に、移動規則を真に理解しているかです。「低い方のポインタを動かす」と繰り返すだけでは証明になりません。優れた回答では、ループ不変条件を述べ、現在の棒がその側の境界を更新するか、それとも境界未満にとどまるかという両方のケースを扱います。その論証により、未走査の領域が今確定した水量を変化させ得ない理由を示す必要があります。
最後に、代替案を正確に比較できるかです。プレフィックス・サフィックス配列は最も説明が容易です。単調スタックは水平方向の窪みを確定し、関連するスタック問題へ自然に応用できます。2ポインタ法は最も空間消費が少なくなります。3つすべてが正解になり得ますが、空間の上限、証明のスタイル、および拡張性が異なります。
回答前の確認事項
- すべての棒の幅は1ですか？ はい。幅が異なる場合は、各列の水深にその幅を掛けます。
- 高さは非負であることが保証されていますか？ はい。ここでは負の高さに定義された物理的意味はなく、黙ってより深い窪みとして扱ってはなりません。
- 配列は空になり得ますか？ 標準的な制約では空になりません。この実装は空の配列に対して自然に
0を返しますが、APIコントラクトには明記しておくべきです。 - 総量を返しますか、それとも各インデックスの水量を返しますか？ 主な問題では総量のみを返します。インデックスごとの出力には必然的に
O(n)の空間が必要です。 - 定数の補助空間が必須ですか？ はい。そうでなければ、プレフィックスおよびサフィックス配列の方が説明しやすい線形解法です。
- 数値型がオーバーフローする可能性はありますか？ 実際の制約から上限を計算してください。より大きな制約やビット幅の狭い整数型の場合は、より大きな累積変数が必要です。
- 入力は1次元の断面ですか、それとも2次元のグリッドですか？ 1次元です。グリッド内での雨水トラップには、外側から内側への境界拡張が必要です。
- 実装が入力を変更してもよいですか？ 変更する必要はありません。サンプルコードは
heightを読み取るだけです。
30秒回答フレームワーク
「ある棒の上の水量は、その両側の最高値のうち小さい方から、その棒自体の高さを引いたものです。 プレフィックス配列とサフィックス配列を使用すれば線形時間ですべての最大値を計算できますが、O(n) の空間を使用します。 左右のポインタと、それぞれの側からこれまでに走査した最高値である leftMax および rightMax を保持することで、その状態を圧縮できます。 leftMax <= rightMax のとき、既知の右境界は既に少なくとも leftMax と同等以上の高さを持っています。 現在の左の棒が leftMax を更新しない場合、その水量は leftMax - height[left] に確定します。境界を更新する場合、その水量はゼロです。 その後、左ポインタを進めます。もう一方の側も対称です。 各インデックスは1回だけ確定されるため、時間計算量は O(n)、補助空間は O(1) です。」
ステップバイステップの詳細解説
ステップ1：1列あたりの答えを定義する。
以下のように定義します：
L[i] = max(height[0..i])
R[i] = max(height[i..n-1])
water[i] = min(L[i], R[i]) - height[i]L[i] と R[i] の両方に height[i] が含まれているため、どちらも現在の棒より低くなることはなく、計算式でゼロへのクランプ処理を追加する必要はありません。総量はすべての water[i] の合計です。この式は、隣接する棒だけをチェックしてもうまくいかない理由も示しています。遠くにある高い境界が窪み全体の水面を決定することがあるからです。
ステップ2：正しいベースラインを確立する。
| アプローチ | 時間計算量 | 補助空間 | 主な特性 |
|---|---|---|---|
| 各インデックスに対して両側を走査 | O(n^2) | O(1) | 直接的な式、重複した処理 |
| 前置・後置最大値配列 | O(n) | O(n) | 最も実装と証明が容易 |
| 単調減少スタック | O(n) | O(n) | 水平方向に窪みの幅と深さを解決 |
| 2ポインタ | O(n) | O(1) | 各ステップで片側から1列を確定 |
プレフィックス解法では左から右へ L を構築し、右から左へ R を構築してから式を適用します。2ポインタ法は水量の定義を変更するわけではありません。L と R のすべての値を保存する前に、十分な既知の境界を利用して列を確定します。
ステップ3：ループ不変条件を述べる。
各イテレーションの開始時：
leftより厳密に左側のすべてのインデックスは、1列あたりの計算式に従って確定済みである。rightより厳密に右側のすべてのインデックスは正しく確定済みである。leftMaxは走査済み範囲height[0..left-1]の最大値であり、空の範囲の最大値は0である。rightMaxはheight[right+1..n-1]の最大値であり、同様に空の範囲には0を使用する。waterはすべての確定済みインデックスの合計である。
未処理の区間は常に [left, right] です。各イテレーションでは、この区間を狭める前に、少なくとも一方の端を恒久的に確定できることを証明しなければなりません。
ステップ4：既知の境界が小さい方の側を動かしてよい理由を証明する。
leftMax <= rightMax であると仮定し、height[left] について考えます：
- 現在の棒が
leftMaxより高い場合、それが新しい左側の最大境界になります。その棒自体が自身の左境界となるため、そこに溜まる水量は0です。 - 現在の棒が
leftMax以下の高さである場合、その右側にある真の最大値は少なくとも既に観測されたrightMax以上であり、rightMax >= leftMaxとなります。したがって、より小さい方の境界はleftMaxに確定し、水量は正確にleftMax - height[left]となります。
どちらの場合も未走査の中央部分の正確な形状を必要としないため、左側の列を確定できます。leftMax > rightMax の場合、証明は右側の列に対して対称になります。これは既知の最大境界の比較であり、隣接する棒に基づいた推測ではありません。
ステップ5：2ポインタアルゴリズムを実装する。
def trap(height: list[int]) -> int:
left = 0
right = len(height) - 1
left_max = 0
right_max = 0
water = 0
while left <= right:
if left_max <= right_max:
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return water条件が left <= right であるため、ポインタが出会ったときに最後の列が確定されます。差分を加算する前に境界を更新することで、新しい最大値の寄与をゼロにし、すべての加算値を非負に保ちます。空の配列の場合、right は -1 から始まり、ループは実行されずに関数は 0 を返します。
ステップ6：[4, 2, 0, 3, 2, 5] をトレースする。
index height side boundary after update added water total
0 4 left leftMax=4 0 0
5 5 right rightMax=5 0 0
1 2 left leftMax=4 2 2
2 0 left leftMax=4 4 6
3 3 left leftMax=4 1 7
4 2 left leftMax=4 2 9高さ 5 の棒は、残りのすべての左側の列に対して十分な高さの既知の右境界を提供するため、アルゴリズムは左側を確定し続けます。すべての列が正確に1回現れ、重複してカウントされる窪みはありません。
ステップ7：終了性、正当性、および計算量を証明する。
初期状態では、処理された両方の範囲は空であるため不変条件が成り立ちます。ステップ4では、各イテレーションで追加される列が正確にその列の水量を受け取ることを証明しています。leftMax または rightMax を更新することで、次のイテレーションのための定義が維持されます。各イテレーションは left をインクリメントするか right をデクリメントします。有限ステップの後、left > right となります。その時点で各インデックスは正しく確定されているため、合計は正しくなります。
各インデックスは1回だけ訪問されるため、時間計算量は O(n) です。アルゴリズムは、出力不要のスカラー結果以外に入力サイズに依存するストレージを割り当てません。2つのポインタ、2つの境界、および1つの累積変数で O(1) の補助空間を使用します。
ステップ8：オラクルおよび対照テストケースで検証する。
固定テストケースには、1本の棒、2本の棒、すべて0、狭義の単調増加・単調減少入力、すべて同じ高さ、複数の独立した窪み、平らな底を持つ窪み、標準的なサンプル例、および [3, 0, 3] を含めるべきです。最後のケースは、誤って left < right を使用して合流地点のインデックスをスキップしてしまう実装を検出します。
短いランダムな非負配列に対して、L と R を構築し、1列あたりの式をオラクルとして使用して2ポインタの結果と比較します。また、結果が非負であること、配列を反転しても合計が変わらないこと、いずれかの両端に高さ0の棒を追加しても元の合計が変わらないことを確認します。差分テストは実装エラーを見つけるためのものであり、不変条件の証明が正当性の根拠であり続けます。
模範解答の例
「まず問題をインデックスごとの式に落とし込みます。i での水深は min(max(height[0..i]), max(height[i..n-1])) - height[i] です。2つのプレフィックス配列を使用すれば、この式を O(n) 時間および O(n) 空間で実装できます。定数の補助空間を満たすために、2ポインタ法を使用します。
ループ内では、leftMax と rightMax は2つのポインタの外側で走査済みの最も高い棒を表します。leftMax <= rightMax の場合、左ポインタを確定します。その現在の棒が leftMax を引き上げる場合、その水量はゼロです。そうでなければ、既知の rightMax は既に少なくとも左境界と同じ高さであるため、未知の中央部分が小さい方の境界を leftMax 未満に下げることはできません。水量は leftMax - height[left] に確定します。その後、左ポインタを内側に進めます。右側も対称です。
各イテレーションで1つの列が恒久的に処理されるため、終了時にはすべての列が完了します。時間は O(n) であり、ポインタ、境界、累積変数は O(1) の補助空間を使用します。短い入力、単調配列や均一配列、複数の窪み、[3, 0, 3] でテストし、短いランダムケースをプレフィックス配列の計算式と差分比較します。」
よくある間違い
- 2つの最大値のうち大きい方から引いてしまう → 水は低い方の境界から溢れ出ます → 常に小さい方の最大値を使用してください。
- 隣接する棒だけをチェックする → 遠くの境界が無視されます → 完全な左右の1列ごとの計算式から出発してください。
- 現在の境界を更新する前に加算してしまう → 新しい最大値によって負の水量が生成される可能性があります → 最初に更新し、その後非負の差分を加算してください。
left < rightを使用する →[3, 0, 3]の中央部分が未処理のままになる可能性があります → ループに出会う位置を含めてください。- 証明なしに大きい境界側のポインタを動かす → 未知の反対側がより低い水面を決定する可能性があります → 既知の反対側の境界によって裏付けられている側のみを確定してください。
- Container With Most Water の計算式を適用してしまう →
width × boundary heightでは棒と列が重複カウントされます → 各棒の上の水深を合計してください。 - イテレーションあたりの作業が定数であることだけで分析を終えてしまう → 将来の棒が答えを変えられない理由を説明していません → 境界の不変条件と2つのケースの証明を述べてください。
- 単調スタックも
O(1)空間を使用すると主張する → 単調な入力ではn個のインデックスが保持される可能性があります → 最悪計算量O(n)の空間を報告してください。 - 図示された例のみをテストする → ポインタの合流、単調、および等高の境界が未検証のままになります → 固定ケースとプレフィックス配列オラクルを追加してください。
フォローアップの質問と回答
フォローアップ1：なぜ height[left] と height[right] を直接比較しないのですか？
現在の端点の高さを比較する別の正しい定式化もありますが、それに対応する不変条件と更新順序が必要です。この実装で leftMax と rightMax を比較しているのは、これらの値が1列あたりの境界式に直接対応するためです。一方の定式化の条件ともう一方の定式化の証明を混在させないでください。1つを選択し、コード、説明、証明の一貫性を保ちましょう。
フォローアップ2：各棒の上の水量を返す必要がある場合はどうしますか？
確定した各増加分を長さ n の配列に書き込み、それを合計するか同時に総量を累積します。実行時間は O(n) のままで、出力自体に O(n) の空間が必要になります。呼び出し元が結果をストリームとして消費する場合、2ポインタ法はインデックスを左から右の順序で確定しないことに注意してください。インデックスを含めるか、完成した出力を並べ替える必要があります。
フォローアップ3：高さが左から右へのストリームとしてのみ届く場合はどうしますか？
正確な答えは将来の右境界に依存するため、固定メモリですべての列を即座に確定することはできません。単調スタックを使用すれば開いた窪みを保持し、十分に高い右境界が届いたときに確定できますが、その最悪メモリは依然として O(n) です。厳密なメモリ制限がある場合は、近似、外部ストレージ、または2回目の走査が必要になります。本来の厳密な定数空間の保証を維持することはできません。
フォローアップ4：棒の幅が異なる場合はどうしますか？
棒 i が個別に幅 width[i] を持つ場合、境界の高さのロジックは同じままで、その体積は waterDepth[i] * width[i] になります。入力が不規則な座標と隙間として与えられる場合は、まず各水平区間における高さを定義します。隣接する棒の中心間の距離は、必ずしも棒全体の幅とは限りません。
フォローアップ5：2次元の高さマップで水をトラップするにはどうしますか？
グリッドのセルは外周境界全体によって制約されるため、2方向のポインタでは不十分です。一般的なアルゴリズムでは、すべての境界セルを最小ヒープに挿入し、現在の最も低い境界から内側へ繰り返し拡張します。未訪問のより低い隣接セルはその高さの差を寄与し、境界と隣接セルの高い方がその後の拡張のための有効境界になります。訪問済みセットを使用すると、m × n のグリッドでは O(mn log(mn)) の時間と O(mn) の空間がかかります。
フォローアップ6：単調スタック解法が適しているのはどのような場合ですか？
フォローアップで左右の境界によって閉じられた各窪みを求める場合、水平方向の幅による説明が必要な場合、またはヒストグラム関連の単調スタック問題へ発展させる場合にスタックが自然です。スタックには高さが減少する順にインデックスを格納します。より高い棒が窪みの底をポップし、新しいスタックの先頭と現在の棒がその境界を形成し、アルゴリズムは effective width × new water-layer depth を加算します。 総時間は依然として O(n) であり、最悪ケースの補助空間は O(n) です。