。雨水をためるⅡ

407. 貯水池 II

難易度: 難しい

トピック: 配列、幅優先検索、ヒープ (優先キュー)、行列

2D 標高マップの各セルの高さを表す m x n 整数行列 heightMap が与えられた場合、雨が降った後に蓄積できる水の量を返します。

例 1:

• 入力: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3 ,2,3,1]]
• 出力: 4
• 説明: 雨が降った後、ブロックの間に水が溜まります。
  • 私たちには、それぞれ 1 単位と 3 単位の水が入った 2 つの小さなプールがあります。
  • 節約できる水の総量は4です。

例 2:

• 入力: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3] ]、[3,2,2,2,3],[3,3,3,3,3]]
• 出力: 10

制約:

• m == heightMap.length
• n == heightMap[i].length
• 1
• 0

解決策:

「貯水池 II」問題は、2 次元の標高マップ (行列で表される) 上で雨が降った後に蓄積される水の量を計算する必要がある、難しい計算問題です。この問題は古典的な「貯留層」問題を 2 次元に拡張し、全方向の流れを考慮する必要があるため、解決策がより複雑になります。

重要なポイント

1. 行列表現: heightMap 行列には各セルの高度が含まれます。
2. 境界制約: 水は境界セルから流出できません。
3. ヒープ データ構造: 最小ヒープ (優先キュー) は、水位を動的にシミュレートするために使用されます。
4. 訪問行列: セルへの繰り返しの訪問を避けるために、訪問したノードを追跡します。

メソッド

このソリューションは、Priority Queue (Min Heap) に基づいて、Breadth-First Search (BFS) アプローチを利用します。

1. すべての境界セルを最小ヒープに追加し、訪問済みとしてマークします。
2. セルを高さの昇順に処理します:
   • 各セルについて、隣接するセルに水を「溜め込む」ようにしてください。
   • 隣接セルとその更新された高さの値をヒープにプッシュします。
3. 現在のセルと隣接するセルの高さの差に基づいて、蓄積された水の量を累積します。

計画

1. 初期化:

   • 行列の次元とエッジケースを定義します。
   • 境界セルの最小ヒープを初期化します。
   • 訪問済み行列を作成します。

2. 境界セルを挿入:

   • すべての境界セルとその高さの値をヒープにプッシュします。
   • 訪問済みとしてマークします。

3. BFS トラバーサル:

   • ヒープが空でない場合は、最も高さの低いセルを抽出します。
   • 隣接するものをすべてチェックし、貯水量を計算します:
     • 隣の方が低い場合、高低差により貯水量が増加します。
     • 隣のセルの方が高い場合は、隣のセルの高さを現在のセルの高さに更新します。
   • 近隣ノードをヒープにプッシュし、訪問済みとしてマークします。

4. 結果を返します:

   • 蓄積水量は、蓄積された雨水の量を表します。

このソリューションを PHP で実装してみましょう: 407. Reservoir II

<?php
/**
 * @param Integer[][] $heightMap
 * @return Integer
 */
function trapRainWater($heightMap) {
    // ...  (解决方案代码将在此处) ...
}

// 示例用法
$heightMap1 = [[1, 4, 3, 1, 3, 2], [3, 2, 1, 3, 2, 4], [2, 3, 3, 2, 3, 1]];
$heightMap2 = [[3, 3, 3, 3, 3], [3, 2, 2, 2, 3], [3, 2, 1, 2, 3], [3, 2, 2, 2, 3], [3, 3, 3, 3, 3]];

echo trapRainWater($heightMap1) . "\n"; // 输出：4
echo trapRainWater($heightMap2) . "\n"; // 输出：10
?>

説明:

1. 境界の初期化:

   • すべての境界セルがパイルに追加されて、コンテナーの外壁が形成されます。

2. ヒープ抽出:

   • 水が内側には流れず外側にのみ流れるようにするために、最も高さが低いセルを抽出します。

3. 近隣探索:

   • 各近隣者:
     • 範囲内にあるか、アクセスされていないかを確認します。
     • 溜まった水の量をmax(0, currentHeight - neighborsHeight)として計算します。
     • 更新された隣接高さをヒープにプッシュします。

4. 蓄積水:

   • 各隣人の貯水量を合計に加えます。

サンプルウォークスルー

次のように入力します:

<code>$heightMap = [
    [1, 4, 3, 1, 3, 2],
    [3, 2, 1, 3, 2, 4],
    [2, 3, 3, 2, 3, 1]
];</code>

手順:

1. 境界セル:

   • 境界セルとその高さをヒープにプッシュします:
     • 例: (0, 0, 1)、(0, 1, 4) など。

2. ヒープトラバーサル:

   • セル (0, 0, 1) (最も低い高さ) を抽出します。
   • 近隣住民を確認し、節水量を計算します:
     • 近隣 (1, 0) の場合: 蓄積された水 = max(0, 1 - 3) = 0。

3. 節水:

   • すべてのセルにアクセスするまで処理を続けます:
     • 節約された水の総量 = 4。

時間計算量

1. ヒープ操作:

   • 各セルはヒープに 1 回プッシュおよびポップされます: O(m n log(m * n))。

2. 近隣反復:

   • 各セルには最大 4 つの隣接セルがあります: O(m * n)。

全体の複雑さ:

*O(m n log(m n))**

出力例

<code>$heightMap = [
    [1, 4, 3, 1, 3, 2],
    [3, 2, 1, 3, 2, 4],
    [2, 3, 3, 2, 3, 1]
];
echo trapRainWater($heightMap); // 输出：4</code>

「リザーバー II」問題は、BFS と組み合わせた優先キューなどの高度なデータ構造の力を示しています。 2D 標高マップで水の流れをシミュレーションすることで、貯留される水の総量を効率的に計算できます。ログ ヒープ操作により、このソリューションは大規模な行列の処理に最適です。

(完全な PHP ソリューション コードをここに含める必要があります。スペースの制限があるため、ここでは提供できません。完全なコード実装については、元の問題の説明にある ./solution.php ファイルを参照してください。)

以上が。雨水をためるⅡの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。