Temu Duga Pengekodan: Bagaimana Anda Menyelesaikan Trapping Rain Water dengan Two Pointers?

Masalah dan Senario yang Berkenaan

Diberikan satu tatasusunan integer bukan negatif height dengan panjang n, height[i] ialah ketinggian bar pada indeks i, dan setiap bar mempunyai lebar 1. Kira jumlah air hujan yang terperangkap oleh bar-bar ini. Sebagai contoh:

height = [4, 2, 0, 3, 2, 5]
result = 9

Sasarannya ialah masa O(n) dan ruang bantuan O(1). Kekangan standard ialah 1 <= n <= 20000 dan 0 <= height[i] <= 100000. Ketinggian tidak pernah negatif, dan masalah utama tidak meminta air yang disimpan di atas setiap bar secara berasingan.

Terdapat bukti temu duga awam secara langsung bagi soalan ini. Laporan Jun 2025 daripada temu duga latihan amali backend Go Baidu menyenaraikan Trapping Rain Water sebagai salah satu daripada tiga tugasan pengekodan langsung. Laporan saringan telefon awam yang berasingan menambah satu varian di mana sejumlah air yang terhad dituangkan pada kedudukan terpilih. Halaman masalah LeetCode bahasa Inggeris dan bahasa Cina mengklasifikasikannya sebagai sukar (hard) dan melabelkannya dengan tatasusunan, two pointers, pengaturcaraan dinamik, tindanan (stack), dan tindanan monotonik (monotonic stack). Kemahiran terasnya ialah menerbitkan dan membuktikan algoritma linear daripada formula tempatan, jadi kategorinya ialah coding tanpa mengira bahasa pelaksanaan atau keluarga pekerjaan.

Perkara yang Dinilai oleh Penemu Duga

Pertama, bolehkah anda menyatakan jumlah yang betul di atas satu bar? Paras air pada indeks i dihadkan oleh yang lebih pendek antara bar tertinggi di sebelah kirinya dan bar tertinggi di sebelah kanannya, bukan oleh dua bar yang bersebelahan secara langsung. Jika leftMax[i] dan rightMax[i] kedua-duanya merangkumi indeks i, jumlahnya ialah min(leftMax[i], rightMax[i]) - height[i].

Kedua, bolehkah anda memampatkan tatasusunan awalan (prefix) dan akhiran (suffix) ke dalam ruang malar? Menyimpan setiap maksimum kiri dan kanan menghasilkan penyelesaian masa O(n) yang mudah. Two pointers menggunakan pemerhatian yang lebih kukuh bahawa sempadan terkecil yang diketahui sudah mencukupi untuk memuktamadkan satu sisi, satu lajur pada satu masa.

Ketiga, adakah anda benar-benar memahami peraturan pergerakannya? Mengulangi "gerakkan penunjuk yang lebih pendek" bukanlah satu bukti. Jawapan yang kukuh menyatakan invariant gelung dan mengendalikan kedua-dua kes: bar semasa sama ada menaikkan sempadan sisinya atau kekal di bawahnya. Hujah tersebut mesti menunjukkan sebab kawasan yang belum diimbas tidak boleh mengubah jumlah air yang baru dimuktamadkan.

Akhir sekali, bolehkah anda membandingkan alternatif dengan tepat? Tatasusunan awalan dan akhiran adalah yang paling mudah diterangkan. Tindanan monotonik menyelesaikan lembangan secara mendatar dan beralih secara semula jadi kepada masalah tindanan yang berkaitan. Two pointers menggunakan ruang paling sedikit. Ketiga-tiganya boleh menjadi betul, tetapi mempunyai batas ruang, gaya pembuktian, dan peluasan yang berbeza.

Soalan Penjelasan Sebelum Menjawab

• Adakah setiap bar mempunyai lebar 1? Ya. Dengan lebar yang berbeza-beza, darabkan kedalaman air bagi setiap lajur dengan lebarnya.
• Adakah ketinggian dijamin bukan negatif? Ya. Ketinggian negatif tidak mempunyai makna fizikal yang ditakrifkan di sini dan tidak boleh secara senyap-senyap menjadi lubang yang lebih dalam.
• Bolehkah tatasusunan menjadi kosong? Kekangan standard menyatakan tidak. Pelaksanaan ini secara semula jadi mengembalikan 0 untuk tatasusunan kosong, tetapi kontrak API masih patut menyatakannya secara eksplisit.
• Adakah kita mengembalikan jumlah keseluruhan atau jumlah pada setiap indeks? Masalah utama hanya mengembalikan jumlah keseluruhan. Output bagi setiap indeks sememangnya memerlukan ruang O(n).
• Adakah ruang bantuan malar diperlukan? Ya. Jika tidak, tatasusunan awalan dan akhiran merupakan penyelesaian linear yang lebih mudah untuk disampaikan.
• Bolehkah jenis numerik mengalami limpahan (overflow)? Kira batas atas daripada kekangan sebenar. Kekangan yang lebih besar atau jenis integer yang sempit memerlukan penumpuk yang lebih luas.
• Adakah input berupa profil satu dimensi atau grid dua dimensi? Ia adalah satu dimensi. Memerangkap air dalam grid memerlukan pengembangan sempadan dari luar ke dalam.
• Bolehkah pelaksanaan mengubah suai input? Tidak perlu; sampel hanya membaca height.

Rangka Jawapan 30 Saat

"Air di atas satu bar ialah nilai yang lebih kecil antara bar tertinggi pada kedua-dua sisinya tolak ketinggian bar tersebut. Tatasusunan awalan dan akhiran mengira semua maksimum tersebut dalam masa linear tetapi menggunakan ruang O(n). Saya boleh memampatkan keadaan tersebut ke dalam penunjuk kiri dan kanan serta leftMax dan rightMax, iaitu bar tertinggi yang telah diimbas dari setiap sisi. Apabila leftMax <= rightMax, sempadan kanan yang diketahui sudah sekurang-kurangnya setinggi leftMax. Jika bar kiri semasa tidak menaikkan leftMax, jumlah airnya ditetapkan pada leftMax - height[left]; jika ia menaikkan sempadan, jumlah airnya adalah sifar. Saya kemudian memajukan penunjuk kiri. Sisi yang satu lagi adalah simetri. Setiap indeks dimuktamadkan sekali, jadi masanya ialah O(n) dan ruang bantuannya ialah O(1)."

Perincian Langkah demi Langkah

Langkah 1: Tentukan jawapan untuk satu lajur.

Katakan:

L[i] = max(height[0..i])
R[i] = max(height[i..n-1])
water[i] = min(L[i], R[i]) - height[i]

Kedua-dua L[i] dan R[i] merangkumi height[i], jadi tiada satu pun yang boleh lebih rendah daripada bar semasa dan formula tersebut tidak memerlukan pemotongan (clamp) tambahan kepada sifar. Jumlah keseluruhan ialah hasil tambah semua water[i]. Formula ini juga menunjukkan sebab menyemak bar bersebelahan sahaja akan gagal: sempadan yang lebih tinggi di kejauhan boleh menetapkan permukaan bagi keseluruhan lembangan.

Langkah 2: Wujudkan garis dasar yang betul.

Penyelesaian awalan membina L dari kiri ke kanan dan R dari kanan ke kiri, kemudian menggunakan formula tersebut. Two pointers tidak mentakrifkan semula jumlah air. Ia menggunakan sempadan mencukupi yang diketahui untuk memuktamadkan satu lajur sebelum menyimpan setiap nilai L dan R.

Langkah 3: Nyatakan invariant gelung.

Pada permulaan setiap lelaran:

1. Setiap indeks yang berada betul-betul di sebelah kiri left telah dimuktamadkan mengikut formula setiap lajur.
2. Setiap indeks yang berada betul-betul di sebelah kanan right telah dimuktamadkan dengan betul.
3. leftMax ialah nilai maksimum julat yang telah diimbas height[0..left-1], dengan nilai maksimum kosong ialah 0.
4. rightMax ialah nilai maksimum height[right+1..n-1], sekali lagi menggunakan 0 untuk julat kosong.
5. water ialah jumlah keseluruhan untuk semua indeks yang telah dimuktamadkan.

Selang yang belum diproses sentiasa [left, right]. Setiap lelaran mesti membuktikan bahawa sekurang-kurangnya satu hujung boleh dimuktamadkan secara kekal sebelum mengecilkan selang ini.

Langkah 4: Buktikan mengapa sisi dengan sempadan yang lebih kecil boleh bergerak.

Katakan leftMax <= rightMax dan pertimbangkan height[left]:

• Jika bar semasa lebih tinggi daripada leftMax, ia menjadi sempadan kiri tertinggi yang baharu. Bar tersebut adalah

sempadan kirinya sendiri, jadi jumlah yang terperangkap ialah 0.

• Jika bar semasa tidak lebih tinggi daripada leftMax, maksimum sebenar di sebelah kanannya adalah sekurang-kurangnya sebesar

rightMax yang telah diperhatikan, dan rightMax >= leftMax. Oleh itu, sempadan yang lebih kecil ditetapkan pada leftMax, menjadikan jumlahnya tepat leftMax - height[left].

Kedua-dua kes tidak memerlukan bentuk tepat bahagian tengah yang belum diimbas, jadi lajur kiri boleh dimuktamadkan. Jika leftMax > rightMax, pembuktiannya adalah simetri untuk lajur kanan. Ini merupakan perbandingan sempadan maksimum yang diketahui, bukan tekaan berdasarkan bar yang bersebelahan.

Langkah 5: Laksanakan algoritma two-pointer.

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

Syaratnya ialah left <= right, jadi lajur terakhir dimuktamadkan apabila kedua-dua penunjuk bertemu. Mengemas kini sempadan sebelum menambah perbezaan memastikan maksimum baharu menyumbang sifar dan mengekalkan setiap kenaikan sebagai bukan negatif. Bagi tatasusunan kosong, right bermula pada -1, gelung tidak berjalan, dan fungsi mengembalikan 0.

Langkah 6: Surih [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

Bar dengan ketinggian 5 membekalkan sempadan kanan yang diketahui cukup tinggi untuk setiap lajur kiri yang tinggal, jadi algoritma terus memuktamadkan sisi kiri. Setiap lajur muncul tepat sekali, tanpa ada lembangan yang dikira dua kali.

Langkah 7: Buktikan penamatan, ketepatan, dan kerumitan.

Pada mulanya, kedua-dua julat yang diproses adalah kosong, jadi invariant adalah benar. Langkah 4 membuktikan bahawa lajur yang ditambah dalam setiap lelaran menerima tepat jumlah bagi setiap lajurnya. Mengemas kini leftMax atau rightMax mengekalkan takrifannya untuk lelaran seterusnya. Setiap lelaran sama ada menaikkan left atau menurunkan right; selepas beberapa langkah yang terhingga, left > right. Pada ketika itu setiap indeks telah dimuktamadkan dengan betul, jadi jumlah keseluruhannya adalah tepat.

Setiap indeks dilawati sekali, memberikan masa O(n). Algoritma ini tidak memperuntukkan storan bersaiz input selain daripada hasil skalar bebas output; dua penunjuk, dua sempadan, dan satu penumpuk menggunakan ruang bantuan O(1).

Langkah 8: Sahkan terhadap oracle formula dan kes adversari.

Ujian tetap harus merangkumi satu bar, dua bar, semua sifar, input yang meningkat dan menurun secara ketat (strictly increasing and decreasing), semua ketinggian sama, beberapa lembangan berasingan, lembangan dengan dasar rata, contoh standard, dan [3, 0, 3]. Kes terakhir mendedahkan pelaksanaan yang salah menggunakan left < right dan melangkau indeks pertemuan.

Bagi tatasusunan bukan negatif rawak yang pendek, bina L dan R, gunakan formula setiap lajur sebagai oracle, dan bandingkannya dengan hasil two-pointer. Semak juga bahawa hasilnya bukan negatif, menyongsangkan tatasusunan mengekalkan jumlah keseluruhan, dan menambah bar berketinggian sifar pada mana-mana hujung luar tidak mengubah jumlah asal. Ujian kebezaan mencari ralat pelaksanaan; bukti invariant kekal sebagai hujah ketepatan.

Contoh Jawapan yang Kukuh

"Mula-mula saya mengurangkan masalah kepada formula bagi setiap indeks. Kedalaman pada i ialah min(max(height[0..i]), max(height[i..n-1])) - height[i]. Dua tatasusunan awalan melaksanakan formula tersebut dalam masa O(n) dan ruang O(n). Untuk memenuhi ruang bantuan malar, saya menggunakan two pointers.

Di dalam gelung, leftMax dan rightMax ialah bar tertinggi yang telah diimbas di luar kedua-dua penunjuk. Jika leftMax <= rightMax, saya memuktamadkan penunjuk kiri. Jika bar semasanya menaikkan leftMax, jumlahnya adalah sifar. Jika tidak, rightMax yang diketahui sudah sekurang-kurangnya setinggi sempadan kiri, jadi bahagian tengah yang tidak diketahui tidak boleh mengurangkan sempadan yang lebih kecil di bawah leftMax; jumlahnya ditetapkan pada leftMax - height[left]. Saya kemudian menggerakkan penunjuk kiri ke dalam. Sisi kanan adalah simetri.

Setiap lelaran mengendalikan satu lajur secara kekal, jadi semua lajur selesai semasa penamatan. Masanya ialah O(n), dan penunjuk, sempadan, serta penumpuk menggunakan ruang bantuan O(1). Saya akan menguji input pendek, tatasusunan monoton dan sama tinggi, beberapa lembangan, serta [3, 0, 3], kemudian membandingkan kes-kes rawak pendek secara pembezaan dengan formula tatasusunan awalan."

Kesilapan Lazim

• Menolak daripada nilai maksimum yang lebih besar antara dua maksimum → Air melimpah melepasi sempadan yang lebih pendek → Sentiasa gunakan maksimum yang lebih kecil.
• Hanya menyemak bar bersebelahan → Sempadan yang jauh diabaikan → Mulakan daripada formula setiap lajur kiri/kanan yang lengkap.
• Menambah sebelum mengemas kini sempadan semasa → Maksimum baharu boleh menghasilkan jumlah negatif → Kemas kini dahulu, kemudian tambah perbezaan bukan negatif.
• Menggunakan left < right → Bahagian tengah [3, 0, 3] boleh kekal tidak diproses → Sertakan kedudukan pertemuan dalam gelung.
• Menggerakkan sisi sempadan yang lebih besar tanpa bukti → Sisi bertentangan yang tidak diketahui mungkin masih menetapkan permukaan yang lebih rendah → Muktamadkan hanya sisi yang disokong oleh sempadan bertentangan yang diketahui.
• Menggunakan formula Container With Most Water → width × boundary height mengira bar dan lajur sebanyak dua kali → Jumlahkan kedalaman air di atas setiap bar.
• Menghentikan analisis pada kerja malar bagi setiap lelaran → Ia tidak menerangkan sebab bar masa depan tidak boleh mengubah jawapan → Nyatakan invariant sempadan dan bukti dua kes.
• Mendakwa bahawa tindanan monotonik juga menggunakan ruang O(1) → Input yang monoton boleh mengekalkan n indeks → Laporkan ruang kes terburuk O(n).
• Hanya menguji contoh yang diilustrasikan → Pertemuan, monotonik, dan sempadan sama tinggi kekal tidak disemak → Tambah kes tetap dan oracle tatasusunan awalan.

Soalan Susulan dan Maklum Balas

Soalan Susulan 1: Mengapa tidak membandingkan height[left] dan height[right] secara langsung?

Satu lagi formulasi yang betul membandingkan ketinggian titik hujung semasa, tetapi ia memerlukan invariant dan urutan kemas kini yang sepadan. Pelaksanaan ini membandingkan leftMax dan rightMax kerana nilai-nilai tersebut memetakan secara langsung kepada formula sempadan setiap lajur. Jangan gabungkan syarat satu formulasi dengan bukti formulasi yang lain; pilih satu dan pastikan kod, penjelasan, serta bukti kekal konsisten.

Soalan Susulan 2: Bagaimana jika fungsi mesti mengembalikan air di atas setiap bar?

Tulis setiap kenaikan yang dimuktamadkan ke dalam tatasusunan dengan panjang n, kemudian jumlahkannya atau kumpulkan jumlah keseluruhan pada masa yang sama. Masa pelaksanaan kekal O(n), manakala output itu sendiri memerlukan ruang O(n). Jika pemanggil menggunakan hasil sebagai strim, ambil perhatian bahawa two pointers tidak memuktamadkan indeks mengikut urutan kiri-ke-kanan; sertakan indeks atau susun semula output yang telah lengkap.

Soalan Susulan 3: Bagaimana jika ketinggian hanya tiba sebagai strim dari kiri ke kanan?

Jawapan yang tepat bergantung pada sempadan kanan masa depan, jadi setiap lajur tidak boleh dimuktamadkan serta-merta dengan memori tetap. Tindanan monotonik boleh mengekalkan lembangan terbuka dan menyelesaikannya apabila sempadan kanan yang cukup tinggi tiba, tetapi memori kes terburuknya masih O(n). Batas memori yang ketat memerlukan anggaran, storan luaran, atau laluan kedua; ia tidak dapat mengekalkan janji ruang malar tepat yang asal.

Soalan Susulan 4: Bagaimana jika bar mempunyai lebar yang berbeza?

Jika bar i secara bebas merangkumi width[i], logik ketinggian sempadan kekal sama dan isipadunya ialah waterDepth[i] * width[i]. Jika input sebaliknya memberikan koordinat dan jurang yang tidak sekata, tentukan dahulu ketinggian merentasi setiap selang mendatar. Jarak antara pusat bar yang bersebelahan tidak secara automatik menjadi lebar keseluruhan bar.

Soalan Susulan 5: Bagaimana anda memerangkap air pada peta ketinggian dua dimensi?

Satu sel grid dihadkan oleh keseluruhan sempadan luar, jadi dua penunjuk berarah tidak mencukupi. Algoritma lazim memasukkan semua sel sempadan ke dalam min-heap dan berulang kali mengembang ke dalam dari sempadan semasa yang paling rendah. Jiran belum dilawati yang lebih rendah menyumbang perbezaan ketinggian, dan ketinggian yang lebih besar antara sempadan dan jiran menjadi sempadan berkesan untuk pengembangan seterusnya. Dengan set dilawati, grid m × n mengambil masa O(mn log(mn)) dan ruang O(mn).

Soalan Susulan 6: Bilakah penyelesaian tindanan monotonik lebih disukai?

Tindanan adalah wajar apabila soalan susulan bertanyakan tentang setiap lembangan yang ditutup oleh sempadan kiri dan kanan, untuk penjelasan lebar mendatar, atau untuk peralihan kepada masalah tindanan monotonik gaya histogram. Ia menyimpan indeks mengikut urutan ketinggian yang menyusut. Bar yang lebih tinggi mengeluarkan (pop) dasar lembangan; bahagian atas tindanan baharu dan bar semasa membentuk sempadannya, dan algoritma menambah effective width × new water-layer depth. Jumlah masa masih O(n), dengan ruang bantuan kes terburuk O(n).