Trapping Rain Water
Bir sıra çubuk yan yana durur; her biri bir birim genişliğindedir: height[i], i çubuğunun yüksekliğidir. Yağmur suyu çubukların arasındaki çukurlarda birikir. Su, yalnızca hem solunda hem de sağında daha uzun bir çubuk varsa bir çubuğun üzerinde kalır; ilk ve son çubuğun ötesinde akıp gider. Sıranın tuttuğu toplam su birimi sayısını döndürün.
Fonksiyon
- heightinteger-array
- her çubuğun yüksekliği, soldan sağa
- Döndürürinteger
- hapsolmuş suyun toplam birim miktarı
Kısıtlar
1 ≤ height.length ≤ 2 × 1040 ≤ height[i] ≤ 105- Her çubuk bir birim genişliğindedir ve su ilk çubuğun önünde ya da son çubuğun arkasında birikmez.
Örnekler
- Girdi
- height = [0, 3, 1, 0, 2, 5, 1, 2]
- Çıktı
- 7
- Açıklama
- 3 ile 5 arasındaki seviye 3'tür: 1'in üzerinde 2 birim, 0'ın üzerinde 3, 2'nin üzerinde 1. Sonraki 1, 5 ile 2'nin arasında yer alır; bu nedenle 1 değerini taşır. Böylece 7 eder.
- Girdi
- height = [4, 1, 3, 0, 5]
- Çıktı
- 8
- Açıklama
- Alçak duvar 4 olduğundan, çukur 4. seviyeye kadar dolar: 1'in üzerinde 3 birim, 3'ün üzerinde 1, 0'ın üzerinde 4; toplam 8 eder. Su, 5 önem kazanmadan önce 4'ün üzerinden taşar.
- Girdi
- height = [1, 2, 4, 2, 1]
- Çıktı
- 0
- Açıklama
- Çubuklar 4'e kadar yükselir ve tekrar alçalır. Her çubuğun ötesinde kendisinden daha uzun hiçbir şey olmayan bir tarafı vardır; bu yüzden su akıp gider ve cevap 0 olur.
Ek soru
Çubukların yüksekliklerden oluşan 2B bir ızgara oluşturduğunu ve suyun dört yönden de dışarı akabildiğini varsayalım. Bu durumda hapsolan suyu nasıl hesaplarsın?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Tüm satırı unut ve tek bir çubuğa bak. Su,
içubuğunun üzerinde ne kadar yükselebilir ve bu yüksekliği hangi çubuklar belirler?içubuğunun üzerindeki su seviyesi iki sayıdan küçük olanıdır: başlangıçtanikonumuna kadar olan en yüksek çubuk veikonumundan sona kadar olan en yüksek çubuk.içubuğu, bu seviye ile kendi yüksekliği arasındaki fark kadar su tutar. Her iki çalışan maksimum da bir uçtan diğerine tek geçişte hesaplanabilir.İki maksimumdan yalnızca küçük olanına ihtiyacın var. Her iki uca birer işaretçi koy ve her işaretçinin geçtiği en yüksek çubuğu takip et. Hangi işaretçi daha alçak çubuğun üzerindeyse, o işaretçinin seviyesi kendi güncel maksimumuyla belirlenir: bu suyu ekle ve o işaretçiyi içeri doğru hareket ettir. İşaretçiler buluştuğunda dur.
Çözüm
Bir çubuğun üzerindeki su, her iki yanında uzakta bulunabilen çubuklara bağlıdır. Su seviyesi, solundaki en yüksek çubuk ile sağındaki en yüksek çubuktan daha alçak olanıdır ve çubuk, kendi yüksekliği çıkarıldıktan sonra kalan bu seviyedeki suyu tutar. Yaklaşımlar yalnızca bu iki maksimumu bulma biçimleri açısından farklıdır.
Her çubuğun iki tarafını da tara
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Her i sütunu için, soldaki en yüksek sütunu bulmak üzere 0'dan i'ye kadar, sağdaki en yüksek sütunu bulmak üzere de i'den sona kadar tara; ardından min(leftMax, rightMax) - height[i] değerini ekle. Her iki taramaya da i sütununu dahil etmek, miktarın negatif olmasını önler ve uçlardaki sütunlara 0 verir.
Her sütun satırın tamamını okur: n = 2 × 10^4, 4 × 10^8 okuma anlamına gelir; bunların çoğu, önceki sütunun taramasını tekrarlar.
Algoritma
waterdeğişkenini 0 olarak ayarla.- Her
iindeksi için,leftMaxdeğerini bulmak üzere 0'dani'ye kadar tara. rightMaxdeğerini bulmak içini'den son indekse kadar tara.min(leftMax, rightMax) - height[i]değeriniwater'a ekle.waterdeğerini döndür.
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 waterHer iki taraftaki en yüksek çubuğu önceden hesaplayın
Sezgi
0'dan i'ye kadar olan en yüksek çubuk, 0'dan i-1'e kadar olan en yüksek çubuk ile height[i] değerinden büyük olanıdır. Bu nedenle soldan yapılan tek bir geçişte leftMax doldurulur; her öğe kendinden önceki öğeden oluşturulur. Sağdan yapılan tek bir geçişte de rightMax doldurulur. Üçüncü bir geçiş ise formülü uygular.
[0, 3, 1, 0, 2, 5, 1, 2] için min(leftMax[i], rightMax[i]) seviyeleri [0, 3, 3, 3, 3, 5, 2, 2] olur. Yükseklikler çıkarıldığında [0, 0, 2, 3, 1, 0, 1, 0] elde edilir; bunların toplamı 7'dir. İki adet n sayılık dizi pahasına zaman karmaşıklığı O(n)'dir.
Algoritma
leftMaxdeğerlerini soldan sağa doldur:leftMax[0] = height[0], ardındanleftMax[i] = max(leftMax[i-1], height[i]).rightMaxdeğerlerini sağdan sola doldur:rightMax[n-1] = height[n-1], ardındanrightMax[i] = max(rightMax[i+1], height[i]).- Her indeks için
min(leftMax[i], rightMax[i]) - height[i]değerini toplama ekle. - Toplamı döndür.
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 waterAlt tarafı hareket ettiren iki işaretçi
Sezgi
Formül yalnızca daha kısa olan duvara ihtiyaç duyar ve iki işaretçi hangisinin bu duvar olduğunu kanıtlayabilir. left değerini 0’da, right değerini son indekste başlat; her bir işaretçinin geçtiği en yüksek çubuk (kendisi dâhil) olan leftMax ve rightMax değerlerini takip et ve her zaman daha alçak çubuğun bulunduğu işaretçiyi ilerlet. Böylece geçilmiş her çubuk, mevcut iki çubuktan daha yüksek olanından daha yüksek değildir; çünkü bir işaretçi yalnızca diğer işaretçinin altındaki çubuktan daha yüksek olmayan bir çubuğu geçer.
height[left] < height[right] olduğunu varsayalım. Değişmez koşula göre leftMax, left değerinin sağındaki bir çubuk olan height[right] değerinden büyük değildir. Dolayısıyla left için sağ duvar en az leftMax yüksekliğindedir ve işaretçiler arasında ne olursa olsun, onun seviyesi tam olarak leftMax olur. Sağdaki çubuk daha alçak veya eşit olduğunda, simetrik argüman right için durumu çözer.
Algoritma
left = 0,right = n-1,leftMax,rightMaxvewaterdeğerlerini 0 olarak ayarla.left < rightolduğu sürece:height[left] < height[right]ise, gerekiyorsaleftMaxdeğeriniheight[left]değerine yükselt,leftMax - height[left]değerini ekle veleftdeğerini sağa ilerlet.- Aksi takdirde sağ tarafta aynısını yap ve
rightdeğerini sola ilerlet. waterdeğerini döndür. İşaretçilerin buluştuğu çubuk en yüksek çubuktur ve su tutmaz.
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
Tuzaklar ve uç durumlar
- Çalışan maksimumu yükseltmeden önce suyu eklemek.
height[left],leftMaxdeğerinden büyük olduğunda miktar negatiftir ve toplam azalır. - Seviyesi kanıtlanmamış olan daha uzun çubuktaki işaretçiyi hareket ettirmek.
[4, 1, 3, 0, 5]üzerinde bu sürüm 8 yerine 4 döndürür. - Yalnızca en yakın komşulara bakmak.
[3, 0, 2, 0, 1, 0, 4]içinde 1 yüksekliğindeki çubuk, dört ve iki adım uzaktaki çubukların belirlediği 3 seviyesine kadar dolar; cevap 12'dir. - Dizinin uçlarını duvar olarak değerlendirmek. Su bu uçlardan akar; bu nedenle bir çubuk, iki çubuk ya da yalnızca yükselen veya yalnızca alçalan bir sıra 0 su tutar.
Sıkça sorulan sorular3
Trapping Rain Water algoritmasının zaman karmaşıklığı nedir?
İki işaretçili çözüm O(n) zamanda çalışır ve her adımda bir işaretçi içe doğru hareket ettiğinden O(1) ek alan kullanır. leftMax ve rightMax dizilerini kullanan sürüm de O(n) zamanda çalışır ancak O(n) alan kullanır. Her çubuktan başlayarak her iki tarafı da taramak O(n²) karmaşıklığındadır.
Yağmur Suyu Biriktirme Problemi yığın kullanılarak çözülebilir mi?
Evet. Yükseklikleri azalan indekslerden oluşan bir yığın tut. Daha uzun bir çubuk geldiğinde en üsttekini çıkar: Bu, yeni tepe ve mevcut çubukla duvarları oluşturulmuş bir havuzun tabanıdır. (min(two walls) - floor) × (distance between the walls - 1) değerini ekle ve çıkarmaya devam et. Böylece suyu yatay katmanlar hâlinde, O(n) zaman ve alan kullanarak doldurursun.
Trapping Rain Water ile Container With Most Water arasındaki fark nedir?
En Çok Su İçeren Kap probleminde çizgiler hiç yer kaplamaz ve cevap, iki çizgi arasındaki en büyük dikdörtgendir. Burada her çubuk katıdır ve cevap, tüm çubuklardaki su miktarını toplar. Her iki durumda da aynı nedenle kısa kenarı ilerletiriz: sonucu zaten belirlenmiştir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def trap(height):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
height = [0, 3, 1, 0, 2, 5, 1, 2]
Beklenen Çıktı
7