. Memerangkap Air Hujan II

407. Takungan II

Kesukaran: Sukar

Topik: Tatasusunan, carian luas-dahulu, timbunan (baris gilir keutamaan), matriks

Diberikan matriks integer m x n heightMap yang mewakili ketinggian setiap sel dalam peta ketinggian 2D, kembalikan jumlah air yang boleh terkumpul selepas hujan.

Contoh 1:

• Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3 ,2,3,1]]
• Output: 4
• Penjelasan: Selepas hujan, air terperangkap di antara blok.
  • Kami mempunyai dua kolam kecil yang masing-masing memuatkan 1 dan 3 unit air.
  • Jumlah jumlah air yang disimpan ialah 4.

Contoh 2:

• Input: 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]]
• Output: 10

Kekangan:

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

Penyelesaian:

Masalah "Reservoir II" ialah masalah pengiraan yang mencabar yang memerlukan kita mengira jumlah air terkumpul selepas hujan turun pada peta ketinggian dua dimensi (diwakili sebagai matriks). Masalah ini memanjangkan masalah "takungan" klasik kepada dua dimensi, menjadikan penyelesaiannya lebih kompleks kerana aliran ke semua arah perlu dipertimbangkan.

Isi penting

1. Perwakilan Matriks: Matriks heightMap mengandungi ketinggian setiap sel.
2. Kekangan sempadan: Air tidak boleh mengalir keluar dari sel sempadan.
3. Struktur data timbunan: Timbunan minimum (baris gilir keutamaan) digunakan untuk mensimulasikan paras air secara dinamik.
4. Matriks Dilawati: Untuk mengelakkan lawatan berulang ke sel, kami menjejaki nod yang dilawati.

Kaedah

Penyelesaian menggunakan pendekatan Breadth-First Search (BFS), dipandu oleh Baris Keutamaan (Timbunan Min):

1. Tambahkan semua sel sempadan pada timbunan min dan tandainya sebagai dilawati.
2. Proses sel dalam susunan ketinggian yang semakin meningkat:
   • Untuk setiap sel, cuba "menimbun" air di jirannya.
   • Tolak sel jiran dan nilai ketinggiannya yang dikemas kini ke dalam timbunan.
3. Kumpul jumlah air yang terkumpul berdasarkan perbezaan ketinggian antara sel semasa dan jirannya.

Rancang

1. Permulaan:

   • Tentukan dimensi matriks dan sarung tepi.
   • Mulakan timbunan min untuk sel sempadan.
   • Buat matriks yang dilawati.

2. Masukkan sel sempadan:

   • Tolak semua sel sempadan dan nilai ketinggiannya ke dalam timbunan.
   • Tandai sebagai dilawati.

3. Perjalanan BFS:

   • Apabila timbunan tidak kosong, ekstrak sel dengan ketinggian terkecil.
   • Semak semua jirannya dan kira rizab air:
     • Jika jiran lebih rendah, perbezaan ketinggian akan meningkatkan jumlah air yang disimpan.
     • Jika jiran lebih tinggi, kemas kini ketinggian jiran kepada ketinggian sel semasa.
   • Tolak jiran ke dalam timbunan dan tandakannya sebagai dilawati.

4. Hasil pulangan:

   • Isipadu air terkumpul mewakili air hujan yang terkumpul.

Mari laksanakan penyelesaian ini dalam 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
?>

Penjelasan:

1. Permulaan sempadan:

   • Semua sel sempadan ditambah pada longgokan untuk membentuk dinding luar bekas.

2. Pengeluaran timbunan:

   • Ekstrak sel dengan ketinggian paling rendah untuk memastikan air hanya boleh mengalir keluar dan tidak masuk.

3. Penerokaan Jiran:

   • Untuk setiap jiran:
     • Semak sama ada ia berada dalam julat dan tidak diakses.
     • Kira jumlah air terkumpul sebagai max(0, currentHeight - neighborHeight).
     • Tolak ketinggian jiran yang dikemas kini ke dalam timbunan.

4. Air terkumpul:

   • Tambahkan jumlah air simpanan setiap jiran kepada jumlah keseluruhan.

Contoh Panduan

Masukkan:

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

Langkah:

1. Sel sempadan:

   • Tolak sel sempadan dan ketinggiannya ke dalam timbunan:
     • Contohnya: (0, 0, 1), (0, 1, 4), dsb.

2. Perjalanan timbunan:

   • Ekstrak sel (0, 0, 1) (ketinggian terendah).
   • Semak jiran dan kira penjimatan air:
     • Untuk jiran (1, 0): air terkumpul = maks(0, 1 - 3) = 0.

3. Air yang disimpan:

   • Teruskan pemprosesan sehingga semua sel telah dilawati:
     • Jumlah jumlah air yang disimpan = 4.

Kerumitan masa

1. Operasi timbunan:

   • Setiap sel ditolak dan muncul ke dalam timbunan sekali: O(m n log(m * n)).

2. Lelaran Jiran:

   • Setiap sel mempunyai paling banyak 4 jiran: O(m * n).

Jumlah kerumitan:

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

Contoh output

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

Masalah "Reservoir II" menunjukkan kekuatan struktur data lanjutan seperti baris gilir keutamaan digabungkan dengan BFS. Dengan mensimulasikan aliran air dalam peta ketinggian 2D, kita boleh mengira jumlah air yang disimpan dengan cekap. Disebabkan oleh operasi timbunan log, penyelesaian ini adalah optimum untuk memproses matriks besar.

(Kod penyelesaian PHP yang lengkap harus disertakan di sini. Disebabkan keterbatasan ruang, saya tidak dapat menyediakannya di sini. Sila rujuk fail ./solution.php dalam huraian masalah asal untuk pelaksanaan kod yang lengkap.)

Atas ialah kandungan terperinci . Memerangkap Air Hujan II. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!