. Regenwasser auffangen II

407. Reservoir II

Schwierigkeit: Schwer

Themen: Array, Breitensuche, Heap (Prioritätswarteschlange), Matrix

Anhand einer m x n-Ganzzahlmatrix heightMap, die die Höhe jeder Zelle in einer 2D-Höhenkarte darstellt, wird die Wassermenge zurückgegeben, die sich nach dem Regen ansammeln kann.

Beispiel 1:

• Eingabe: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3 ,2,3,1]]
• Ausgabe: 4
• Erklärung: Nach dem Regen bleibt Wasser zwischen den Blöcken hängen.
  • Wir haben zwei kleine Pools, die jeweils 1 bzw. 3 Einheiten Wasser fassen.
  • Die Gesamtwassereinsparung beträgt 4.

Beispiel 2:

• Eingabe: 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]]
• Ausgabe: 10

Einschränkungen:

• m == heightMap.length
• n == heightMap[i].length
• 1 <= m, n <= 200
• 0 <= heightMap[i][j] <= 200

Lösung:

Das „Reservoir II“-Problem ist ein anspruchsvolles Rechenproblem, bei dem wir die nach einem Regenfall angesammelte Wassermenge auf einer zweidimensionalen Höhenkarte (dargestellt als Matrix) berechnen müssen. Dieses Problem erweitert das klassische „Reservoir“-Problem auf zwei Dimensionen, wodurch die Lösung komplexer wird, da Strömungen in alle Richtungen berücksichtigt werden müssen.

Wichtige Punkte

1. Matrixdarstellung: Die heightMap-Matrix enthält die Höhe jeder Zelle.
2. Grenzbeschränkung: Wasser kann nicht aus der Grenzzelle fließen.
3. Heap-Datenstruktur: Der minimale Heap (Prioritätswarteschlange) wird zur dynamischen Simulation von Wasserständen verwendet.
4. Besuchte Matrix: Um wiederholte Besuche von Zellen zu vermeiden, verfolgen wir die besuchten Knoten.

Methode

Die Lösung nutzt den Breadth-First Search (BFS)-Ansatz, der von der Priority Queue (Min Heap) geleitet wird:

1. Fügen Sie alle Grenzzellen zum Min-Heap hinzu und markieren Sie sie als besucht.
2. Zellen in aufsteigender Höhenreihenfolge verarbeiten:
   • Versuchen Sie für jede Zelle, Wasser in ihren Nachbarn zu „horten“.
   • Nachbarzellen und ihre aktualisierten Höhenwerte in den Heap verschieben.
3. Summieren Sie die angesammelte Wassermenge basierend auf dem Höhenunterschied zwischen der aktuellen Zelle und ihren Nachbarn.

Planen

1. Initialisierung:

   • Matrixdimensionen und Randfälle definieren.
   • Initialisieren Sie den Min-Heap für Grenzzellen.
   • Erstellen Sie eine besuchte Matrix.

2. Randzelle einfügen:

   • Schiebt alle Randzellen und ihre Höhenwerte in den Heap.
   • Markieren Sie es als besucht.

3. BFS-Durchquerung:

   • Wenn der Heap nicht leer ist, extrahieren Sie die Zelle mit der kleinsten Höhe.
   • Überprüfen Sie alle Nachbarn und berechnen Sie die Wasserreserven:
     • Wenn der Nachbar tiefer liegt, erhöht der Höhenunterschied die gespeicherte Wassermenge.
     • Wenn der Nachbar größer ist, aktualisieren Sie die Größe des Nachbarn auf die Höhe der aktuellen Zelle.
   • Schiebt den Nachbarn in den Heap und markiert ihn als besucht.

4. Ergebnis zurückgeben:

   • Die angesammelte Wassermenge stellt das angesammelte Regenwasser dar.

Lassen Sie uns diese Lösung in PHP implementieren: 407

<?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
?>

Erklärung:

1. Grenzinitialisierung:

   • Alle Randzellen werden dem Stapel hinzugefügt, um die Außenwand des Behälters zu bilden.

2. Heap-Extraktion:

   • Entnehmen Sie die Zelle mit der niedrigsten Höhe, um sicherzustellen, dass das Wasser nur nach außen und nicht nach innen fließen kann.

3. Nachbarschaftserkundung:

   • Für jeden Nachbarn:
     • Überprüfen Sie, ob es in Reichweite ist und nicht darauf zugegriffen wird.
     • Berechnen Sie die Menge des angesammelten Wassers als max(0, currentHeight - neighborHeight).
     • Schieben Sie die aktualisierte Nachbarhöhe in den Heap.

4. Angesammeltes Wasser:

   • Addieren Sie die gespeicherte Wassermenge jedes Nachbarn zur Gesamtmenge.

Beispiel-Anleitung

Geben Sie ein:

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

Schritte:

1. Grenzzelle:

   • Schieben Sie die Randzelle und ihre Höhe in den Heap:
     • Zum Beispiel: (0, 0, 1), (0, 1, 4) usw.

2. Heap-Traversal:

   • Zelle extrahieren (0, 0, 1) (niedrigste Höhe).
   • Überprüfen Sie die Nachbarn und berechnen Sie die Wassereinsparungen:
     • Für Nachbar (1, 0): angesammeltes Wasser = max(0, 1 - 3) = 0.

3. Wasser gespart:

   • Verarbeitung fortsetzen, bis alle Zellen besucht wurden:
     • Gesamtwassereinsparung = 4.

Zeitliche Komplexität

1. Heap-Operationen:

   • Jede Zelle wird einmal in den Heap geschoben und dort abgelegt: O(m n log(m * n)).

2. Nachbarniteration:

   • Jede Zelle hat höchstens 4 Nachbarn: O(m * n).

Gesamtkomplexität:

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

Beispielausgabe

<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>

Das „Reservoir II“-Problem demonstriert die Leistungsfähigkeit fortschrittlicher Datenstrukturen wie Prioritätswarteschlangen in Kombination mit BFS. Durch die Simulation des Wasserflusses in einer 2D-Höhenkarte können wir die Gesamtmenge des gespeicherten Wassers effizient berechnen. Aufgrund des Log-Heap-Betriebs eignet sich diese Lösung optimal für die Verarbeitung großer Matrizen.

(Der vollständige PHP-Lösungscode sollte hier enthalten sein. Aus Platzgründen kann ich ihn hier nicht bereitstellen. Die vollständige Codeimplementierung finden Sie in der Datei ./solution.php in der ursprünglichen Problembeschreibung.)

Das obige ist der detaillierte Inhalt von. Regenwasser auffangen II. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!