Trapping Rain Water
Deretan batang berdiri berdampingan, masing-masing selebar satu unit: height[i] adalah tinggi batang i. Air hujan terkumpul di cekungan di antara batang-batang. Air hanya tertahan di atas sebuah batang jika ada batang yang lebih tinggi di sebelah kiri dan di sebelah kanannya; air mengalir keluar melewati batang pertama dan terakhir. Kembalikan total unit air yang ditampung deretan tersebut.
Fungsi
- heightinteger-array
- tinggi setiap batang, dari kiri ke kanan
- Mengembalikaninteger
- jumlah total unit air yang terperangkap
Batasan
1 ≤ height.length ≤ 2 × 1040 ≤ height[i] ≤ 105- Setiap batang lebarnya satu unit, dan air tidak dapat bertahan melewati batang pertama atau batang terakhir.
Contoh
- Input
- height = [0, 3, 1, 0, 2, 5, 1, 2]
- Output
- 7
- Penjelasan
- Di antara 3 dan 5, tingkatnya adalah 3: 2 unit di atas 1, 3 di atas 0, 1 di atas 2. Angka 1 yang muncul belakangan berada di antara 5 dan 2, jadi nilainya 1. Hasilnya 7.
- Input
- height = [4, 1, 3, 0, 5]
- Output
- 8
- Penjelasan
- Dinding yang lebih rendah adalah 4, jadi cekungan terisi hingga ketinggian 4: 3 unit di atas 1, 1 di atas 3, 4 di atas 0, sehingga jumlahnya 8. Air meluap melewati 4 sebelum 5 berpengaruh.
- Input
- height = [1, 2, 4, 2, 1]
- Output
- 0
- Penjelasan
- Batang-batang naik hingga 4 lalu turun lagi. Setiap batang memiliki sisi yang tidak memiliki apa pun yang lebih tinggi di luarnya, sehingga air mengalir keluar dan jawabannya adalah 0.
Pertanyaan lanjutan
Misalkan batang-batang itu membentuk grid 2D dengan ketinggian tertentu dan air dapat mengalir keluar ke keempat arah. Bagaimana cara menghitung air yang terperangkap?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Lupakan seluruh baris dan perhatikan satu batang. Seberapa tinggi air dapat berada di atas batang
i, dan batang mana yang menentukan ketinggian itu?Ketinggian air di atas batang
iadalah nilai yang lebih kecil dari dua angka: batang tertinggi dari awal hinggai, dan batang tertinggi dariihingga akhir. Batangimenampung air setinggi nilai tersebut dikurangi tinggi batangnya sendiri. Kedua nilai maksimum berjalan dapat dibangun dalam satu kali lintasan dari masing-masing ujung.Kamu hanya memerlukan nilai yang lebih kecil dari dua batas maksimum. Letakkan satu penunjuk di setiap ujung dan catat batang tertinggi yang telah dilewati setiap penunjuk. Level penunjuk yang berada di batang lebih rendah ditentukan oleh nilai maksimum sementara penunjuk itu sendiri: tambahkan air tersebut lalu geser penunjuk itu ke dalam. Berhenti saat kedua penunjuk bertemu.
Solusi
Air di atas sebuah batang bergantung pada batang-batang yang mungkin berada jauh di kedua sisinya. Ketinggian airnya adalah yang lebih kecil antara batang tertinggi di sebelah kiri dan batang tertinggi di sebelah kanan, lalu batang tersebut menampung air setinggi nilai itu dikurangi tinggi batangnya sendiri. Pendekatan yang digunakan hanya berbeda dalam cara mencari kedua nilai maksimum tersebut.
Scan kedua sisi dari setiap batang
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Untuk setiap batang i, telusuri dari 0 hingga i untuk menemukan batang tertinggi di sebelah kiri, lalu dari i hingga akhir untuk menemukan batang tertinggi di sebelah kanan, kemudian tambahkan min(leftMax, rightMax) - height[i]. Menyertakan batang i dalam kedua penelusuran memastikan jumlahnya tidak menjadi negatif dan menghasilkan 0 untuk batang di ujung.
Setiap batang membaca seluruh baris: n = 2 × 10^4 berarti 4 × 10^8 pembacaan, sebagian besar mengulang penelusuran batang sebelumnya.
Algoritma
- Atur
waterke 0. - Untuk setiap indeks
i, telusuri dari 0 hinggaiuntuk mencarileftMax. - Telusuri dari
ihingga indeks terakhir untuk mencarirightMax. - Tambahkan
min(leftMax, rightMax) - height[i]kewater. - Kembalikan
water.
def trap(height):
n = len(height)
water = 0
for i in range(n):
# The tallest bar at or left of i, and the tallest at or right of i.
left_max = 0
for j in range(i + 1):
left_max = max(left_max, height[j])
right_max = 0
for j in range(i, n):
right_max = max(right_max, height[j])
water += min(left_max, right_max) - height[i]
return waterHitung lebih dahulu batang tertinggi di setiap sisi
Intuisi
Batang tertinggi dari 0 hingga i adalah yang lebih tinggi antara batang tertinggi dari 0 hingga i-1 dan height[i]. Jadi, satu kali lintasan dari kiri mengisi leftMax, setiap entri dibangun dari entri sebelumnya, dan satu kali lintasan dari kanan mengisi rightMax. Lintasan ketiga menerapkan rumusnya.
Untuk [0, 3, 1, 0, 2, 5, 1, 2], level min(leftMax[i], rightMax[i]) adalah [0, 3, 3, 3, 3, 5, 2, 2]. Setelah dikurangi tinggi batang, hasilnya adalah [0, 0, 2, 3, 1, 0, 1, 0], yang jumlahnya 7. Waktunya O(n), dengan biaya penggunaan dua array yang masing-masing berisi n angka.
Algoritma
- Isi
leftMaxdari kiri ke kanan:leftMax[0] = height[0], laluleftMax[i] = max(leftMax[i-1], height[i]). - Isi
rightMaxdari kanan ke kiri:rightMax[n-1] = height[n-1], lalurightMax[i] = max(rightMax[i+1], height[i]). - Untuk setiap indeks, tambahkan
min(leftMax[i], rightMax[i]) - height[i]ke total. - Kembalikan total.
def trap(height):
n = len(height)
left_max = [0] * n # tallest bar from index 0 to i
right_max = [0] * n # tallest bar from index i to n-1
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i - 1], height[i])
right_max[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
right_max[i] = max(right_max[i + 1], height[i])
water = 0
for i in range(n):
water += min(left_max[i], right_max[i]) - height[i]
return waterDua pointer yang bergerak di sisi bawah
Intuisi
Rumus ini hanya membutuhkan dinding yang lebih rendah, dan dua pointer dapat membuktikan dinding yang mana. Mulai left dari 0 dan right dari indeks terakhir, lacak leftMax dan rightMax, yaitu batang tertinggi yang telah dilewati setiap pointer, termasuk batang pada posisinya sendiri, dan selalu gerakkan pointer pada batang yang lebih rendah. Dengan begitu, setiap batang yang telah dilewati tidak lebih tinggi daripada batang yang lebih tinggi di antara dua batang saat ini, karena sebuah pointer hanya melangkahi batang yang tidak lebih tinggi daripada batang di bawah pointer yang lain.
Misalkan height[left] < height[right]. Berdasarkan invarian, leftMax paling tinggi sama dengan height[right], yaitu batang di sebelah kanan left. Jadi, dinding kanan left setidaknya setinggi leftMax, dan ketinggian airnya tepat leftMax, apa pun yang berada di antara kedua pointer. Ketika batang kanan lebih rendah atau sama tinggi, argumen kebalikannya berlaku untuk right.
Algoritma
- Tetapkan
left = 0,right = n-1, sertaleftMax,rightMax, danwaterke 0. - Selama
left < right: jikaheight[left] < height[right], naikkanleftMaxmenjadiheight[left]jika perlu, tambahkanleftMax - height[left], lalu geserleftke kanan. - Jika tidak, lakukan hal yang sama di sisi kanan, lalu geser
rightke kiri. - Kembalikan
water. Batang tempat kedua pointer bertemu adalah yang tertinggi dan tidak menampung air.
def trap(height):
left, right = 0, len(height) - 1
left_max = right_max = 0 # tallest bar passed so far from each end
water = 0
while left < right:
if height[left] < height[right]:
# A bar taller than height[left] waits on the right, so left_max sets the level here.
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
# A bar at least as tall as height[right] waits on the left, so right_max sets the level.
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return water
Jebakan dan kasus tepi
- Menambahkan air sebelum memperbarui nilai maksimum sementara. Saat
height[left]lebih besar darileftMax, jumlah airnya negatif dan totalnya berkurang. - Memindahkan pointer pada batang yang lebih tinggi, yang levelnya belum terbukti. Pada
[4, 1, 3, 0, 5], versi itu menghasilkan 4, bukan 8. - Hanya melihat tetangga terdekat. Pada
[3, 0, 2, 0, 1, 0, 4], batang bernilai 1 terisi hingga level 3, yang ditentukan oleh batang yang berjarak empat dan dua langkah; jawabannya adalah 12. - Menganggap ujung array sebagai dinding. Air mengalir keluar di sana, jadi satu batang, dua batang, atau barisan yang hanya naik atau hanya turun menampung 0.
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu untuk Trapping Rain Water?
Solusi dua pointer berjalan dalam waktu O(n) dan menggunakan ruang ekstra O(1), karena setiap langkah menggerakkan satu pointer ke dalam. Versi dengan array leftMax dan rightMax juga berjalan dalam waktu O(n), tetapi menggunakan ruang O(n). Memindai kedua sisi dari setiap batang membutuhkan waktu O(n²).
Bisakah Trapping Rain Water diselesaikan dengan stack?
Ya. Simpan tumpukan indeks dengan tinggi yang menurun. Saat batang yang lebih tinggi tiba, keluarkan elemen teratas: elemen itu menjadi dasar kolam yang dibatasi oleh elemen teratas yang baru dan batang saat ini. Tambahkan (min(two walls) - floor) × (distance between the walls - 1) dan terus keluarkan elemen. Cara ini mengisi air dalam lapisan horizontal, dengan waktu dan ruang O(n).
What is the difference between Trapping Rain Water and Container With Most Water?
Dalam Container With Most Water, garis tidak memakan ruang dan jawabannya adalah persegi panjang terbesar di antara dua garis. Di sini, setiap batang berisi penuh, dan jawabannya menjumlahkan air di semua batang. Pada keduanya, sisi yang lebih rendah digeser karena alasan yang sama: hasilnya sudah ditentukan.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def trap(height):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
height = [0, 3, 1, 0, 2, 5, 1, 2]
Output yang diharapkan
7