Trapping Rain Water
Bir sıra çubuk yan yana durur ve her biri bir birim genişliğindedir: height[i], i çubuğunun yüksekliğidir. Sıranın üzerine yağmur yağar ve çubukların arasındaki çukurlarda birikir. Su, yalnızca hem solunda hem de sağında bir yerde 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 birim kare su miktarını döndürün.
Fonksiyon
- heightinteger-array
- soldan sağa her çubuğun yüksekliği
- Döndürürinteger
- hapsolmuş suyun toplam birim sayısı
Kısıtlar
1 ≤ height.length ≤ 2 × 1040 ≤ height[i] ≤ 105- Her çubuk bir birim genişliğindedir ve su ilk çubuğun öncesinde ya da son çubuğun sonrasında kalmaz.
Örnekler
- Girdi
- height = [0, 3, 1, 0, 2, 5, 1, 2]
- Çıktı
- 7
- Açıklama
- 3 ile 5 arasında su, 3. seviyeye kadar yükselir: 1 yüksekliğindeki sütunun üzerinde 2 birim, 0'ın üzerinde 3 birim ve 2'nin üzerinde 1 birim tutar. Sona yakın olan 1, 5 ile bir 2 arasında yer alır; bu nedenle seviyesi 2'dir ve 1 birim su tutar. 2 + 3 + 1 + 1 = 7.
- Girdi
- height = [4, 1, 3, 0, 5]
- Çıktı
- 8
- Açıklama
- Daha alçak duvar soldaki 4'tür, bu yüzden çukurun tamamı 4 seviyesine kadar dolar: 1'in üzerinde 3 birim, 3'ün üzerinde 1 birim ve 0'ın üzerinde 4 birim; toplamda 8 eder. Sağdaki 5 seviyeyi yükseltmez, çünkü su önce 4'ün üzerinden taşar.
- Girdi
- height = [1, 2, 4, 2, 1]
- Çıktı
- 0
- Açıklama
- Sütunlar 4'e kadar yükselir ve sonra tekrar alçalır. Her sütunun ötesinde daha yüksek hiçbir şey olmayan bir tarafı vardır; bu nedenle su akar gider ve sonuç 0 olur.
Gönderirken +17 gizli test
Ek soru
Çubukların yüksekliklerden oluşan 2B bir ızgara oluşturduğunu ve suyun dört yönden de kaçabildiğini varsayalım. Bu durumda hapsolan suyu nasıl sayarsınız?
İ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 seviyeden kendi yüksekliği çıkarıldığında kalan miktarı tutar. Her iki kümülatif maksimum da iki uçtan başlayarak tek geçişte oluşturulabilir.İki maksimumun küçüğüne 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. Daha alçak çubuğun üzerinde duran işaretçinin seviyesi, kendi o ana kadarki maksimumuyla belirlenir: bu suyu ekle ve o işaretçiyi içeri doğru hareket ettir. İşaretçiler buluştuğunda dur.
Çözüm
Her çubuğun üzerindeki su, her iki tarafta da uzakta olabilen çubuklara bağlıdır; bu yüzden yalnızca komşulara yerel olarak bakmak yanlış sonuç verir. Çözüm tek bir formüldür: Bir çubuğun üzerindeki su seviyesi, solundaki en yüksek çubuk ile sağındaki en yüksek çubuğun küçüğüdür. Her çubuk için bu iki maksimumu tarayarak bulmak yavaştır; bunları iki dizide saklamak işlemi doğrusal hâle getirir ve her zaman daha alçak tarafta ilerleyen iki işaretçi ise hiç dizi gerektirmez.
Her çubuğun iki yanını da tara
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Suyu sütun sütun hesapla. i çubuğunun üzerindeki su, iki duvarından alçak olanın üzerinden taşana kadar yükselir. Sol duvar, 0 indeksinden i indeksine kadar herhangi bir yerdeki en yüksek çubuktur; sağ duvar ise i indeksinden sona kadar olan en yüksek çubuktur. Dolayısıyla su seviyesi min(leftMax, rightMax) olur ve i çubuğunun üzerindeki su miktarı bu seviyeden height[i] çıkarılarak bulunur.
[0, 3, 1, 0, 2, 5, 1, 2] dizisini ve 3 indeksindeki 0 çubuğunu ele al. Solundaki en yüksek çubuk 3, sağındaki ise 5'tir. Su seviyesi 3'tür, yani orada 3 birim su bulunur. 6 indeksindeki 1 için duvarların yükseklikleri 5 ve 2'dir: su seviyesi 2 olur ve 1 birim su tutar.
Her iki tarama da i çubuğunu da içerir. Bu, sonucun negatif olmasını önler: i çubuğu bir taraftaki her şeyden yüksek olduğunda, o taraftaki maksimum değer kendi yüksekliğidir; su seviyesi yüksekliğine eşit olur ve çubuk 0 birim su tutar. İlk ve son çubukların her zaman 0 birim su tutmasının nedeni de budur.
Sorun maliyettir. Her çubuk tüm satırı, yarısını sola ve yarısını sağa doğru tarar; dolayısıyla toplamda n × n okuma yapılır: 2 × 10^4 çubuk için 4 × 10^8 okuma. Taramalar birbirini de tekrarlar: 5 indeksinin solundaki en yüksek çubuk, 4 indeksinin solundaki en yüksek çubukla bir karşılaştırmanın daha eklenmesiyle bulunabilir; kaba kuvvet yöntemi ise bunu sıfırdan yeniden hesaplar.
Algoritma
water'ı 0 olarak ayarla.- Her
iindeksi için,leftMax'i bulmak üzere 0'dani'ye kadar tara. rightMax'i bulmak üzerei'den son indekse kadar tara.min(leftMax, rightMax) - height[i]değeriniwater'a ekle.water'ı 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 hesapla
Sezgi
Formül aynı kalır; yalnızca iki duvarı elde etme şeklin değişir. 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 sağa yapılan tek geçiş, her girdisi bir önceki girdiden oluşturulan bir leftMax dizisini doldurur. Sağdan sola yapılan tek geçiş de aynı şekilde rightMax dizisini doldurur. Üçüncü bir geçişte her çubuk için min(leftMax[i], rightMax[i]) - height[i] eklenir.
[0, 3, 1, 0, 2, 5, 1, 2] için: leftMax = [0, 3, 3, 3, 3, 5, 5, 5] ve rightMax = [5, 5, 5, 5, 5, 5, 2, 2]. Bunların küçük olan değerleri, [0, 3, 3, 3, 3, 5, 2, 2] seviyeleridir. Yükseklikleri çıkarınca [0, 0, 2, 3, 1, 0, 1, 0] elde edersin; bunların toplamı 7'dir.
Her geçiş her çubuğa bir kez dokunur, dolayısıyla zaman karmaşıklığı O(n)'dir: 2 × 10^4 çubuk için yaklaşık 6 × 10^4 adım; 4 × 10^8 adım değil. Bunun bedeli, n sayıdan oluşan iki ek dizidir. Bir mülakatta önce bu yöntemi kullan: hata yapması zordur ve sonraki yaklaşım farklı bir fikir değil, dizileri ortadan kaldırmanın bir yoludur.
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 için iki duvardan yalnızca daha alçak olan gerekir. Sol duvarın bir indekste daha alçak olduğunu kanıtlayabiliyorsan o indeksin sağ duvarına hiç ihtiyacın olmaz. İki işaretçi bu kanıtı sağlar. left işaretçisini 0 indeksine, right işaretçisini son indekse yerleştir ve her iki işaretçinin şimdiye kadar üzerinden geçtiği en yüksek çubukları, üzerinde durdukları çubuklar da dahil olmak üzere, leftMax ve rightMax olarak tut.
Değişmez: işaretçilerin şimdiye kadar üzerinden geçtiği her çubuk, şu anda üzerinde durdukları iki çubuktan daha yüksek olanından daha yüksek değildir. Bu geçerlidir; çünkü her zaman daha alçak çubuğun üzerindeki işaretçiyi hareket ettirirsin, dolayısıyla bir işaretçi yalnızca diğer işaretçinin altındaki çubuktan daha yüksek olmayan bir çubuğu geçer.
Şimdi height[left] < height[right] olduğunu varsayalım. Değişmeze göre leftMax, height[right] değerinden büyük değildir ve height[right] da left işaretçisinin sağındaki bir çubuktur. Dolayısıyla left işaretçisinin gerçek sağ duvarı en az leftMax kadar yüksektir ve işaretçilerin arasında ne olursa olsun left konumundaki seviye tam olarak leftMax olur. leftMax - height[left] değerini ekle ve left işaretçisini bir adım sağa hareket ettir. height[right] daha alçak ya da eşit çubuk olduğunda, sağ tarafta aynı işlemi tersine uygula. Suyu eklemeden önce geçerli maksimumu güncelle; böylece işaretçinin altındaki çubuk kendi duvarı sayılır ve su miktarı asla negatif olmaz.
[0, 3, 1, 0, 2, 5, 1, 2] dizisini adım adım inceleyelim. İşaretçiler 0 ve 2 değerlerinin üzerinde başlar: sol taraf daha alçaktır ve 0 su tutar. Sonra 3 ile 2 karşılaştırılır: sağ taraf daha alçaktır, rightMax 2 olur ve bu konum 0 su tutar. Ardından 3 ile 1 karşılaştırılır: sağ taraf yine daha alçaktır ve 1 değeri 2-1 = 1 birim su tutar. Sonra 3 ile 5 karşılaştırılır: bu kez sol taraf daha alçaktır, leftMax 3 olur; 3 değeri 0, 1 değeri 2, 0 değeri 3 ve 2 değeri 1 birim su tutar. İşaretçiler 5 değerinde buluşur. Toplam, tek geçiş ve dört değişkenle 1 + 2 + 3 + 1 = 7 olur.
Algoritma
left = 0,right = n-1değerlerini ayarlayın veleftMax,rightMaxilewaterdeğerlerini 0 yapın.left < rightolduğu süreceheight[left]ileheight[right]değerlerini karşılaştırın.- Sol çubuk daha alçaksa, gerekiyorsa
leftMaxdeğeriniheight[left]değerine yükseltin,leftMax - height[left]değerini ekleyin veleftdeğerini sağa ilerletin. - Aksi hâlde, gerekiyorsa
rightMaxdeğeriniheight[right]değerine yükseltin,rightMax - height[right]değerini ekleyin verightdeğerini sola ilerletin. - İşaretçiler buluştuğunda
waterdeğerini döndürün; buluştukları çubuk en yüksek çubuktur ve hiç 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
Formül kısadır ve yanlış yanıtların çoğu iki satırın sırasından veya hangi tarafa hareket ettiğinizden kaynaklanır.
- Çalışan maksimumu güncellemeden önce suyu eklemek.
height[left],leftMaxdeğerinden büyükseleftMax - height[left]negatiftir ve toplam küçülür. Önce maksimumu güncelleyin, sonra ekleyin. - Daha yüksek çubuktaki işaretçiyi hareket ettirmek. Seviye yalnızca alçak tarafta bilinir; yüksek tarafı hareket ettirmek, varlığını kanıtlamadığınız bir duvarı kullanır.
[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. Bir çubuğun duvarları uzakta olabilir:
[3, 0, 2, 0, 1, 0, 4]dizisinde 1 yüksekliğindeki çubuk, dört ve iki adım uzaktaki çubukların belirlediği 3 seviyesine kadar su tutar. Buradaki yanıt 12'dir. - Dizinin uçlarını duvar olarak kabul etmek. İlk veya son çubuğun ötesindeki su akıp gider; bu nedenle tek bir çubuk, iki çubuk ya da yalnızca yükselen veya yalnızca alçalan bir sıra 0 su tutar.
- Kaba kuvvet yönteminde çubuk
i'yi kendi taramalarının dışında bırakmak. Bu durumda her iki taraftan da yüksek bir çubuk negatif miktar verir. Çubuğu taramaya dahil edin veya sonucu 0 ile sınırlandırın. - Çarpma kullanan bir varyantta taşma. Burada yanıt yaklaşık 2 × 10^9'a ulaşır (19,998 boş hücrenin iki yanındaki 10^5 yüksekliğinde iki çubuk); bu değer yine de işaretli 32 bitlik bir tam sayıya sığar. Kendi varyantlarınızda 64 bitlik toplamlar kullanın.
Sıkça sorulan sorular4
Trapping Rain Water probleminin zaman karmaşıklığı nedir?
İki işaretçili çözüm O(n) zamanda ve O(1) ek alanda çalışır: her adımda bir işaretçi içeri doğru ilerler, dolayısıyla n-1 adım vardı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ı taramak O(n²) zaman alır; 2 × 10^4 çubuk için yaklaşık 4 × 10^8 okuma gerekir.
İki işaretçili çözüm neden daha kısa olan tarafı hareket ettirebilir?
Geçilmiş her çubuk, yalnızca daha alçak olan işaretçi hareket ettiği için, o anki iki çubuktan daha uzun olanından daha yüksek değildir. Dolayısıyla sol çubuk daha alçak olduğunda, sol taraftaki birikimli maksimum sağ çubuktan büyük değildir ve sağ çubuk sağında gerçek bir duvar oluşturur. İşaretçinin bulunduğu soldaki seviyede, işaretçiler arasında ne olduğundan bağımsız olarak, birikimli maksimum vardır; bu çubuğu kesinleştirip devam edebilirsin.
Yağmur Suyu Tutma problemi yığın kullanılarak çözülebilir mi?
Evet. Yükseklikleri alttan üste doğru azalan indekslerden oluşan bir yığın tut. Tepedekinden daha yüksek bir çubuk geldiğinde tepedeki indeksi çıkar: bu, yığının yeni tepesinin ve mevcut çubuğun duvarlarını oluşturduğu bir havuzun tabanıdır. (min(two walls) - floor) × (distance between the walls - 1) değerini ekle ve mevcut çubuk daha yüksek olduğu sürece yığından eleman çıkarmaya devam et. Yığın, suyu sütunlar yerine yatay katmanlar halinde hesaplar; bu işlem O(n) zamanda ve O(n) alan kullanarak yapılır.
Trapping Rain Water, Container With Most Water'dan nasıl farklıdır?
En Çok Su İçeren Kapta iki çizgi seçersin ve aralarındaki çizgiler yer kaplamaz; bu yüzden cevap tek bir dikdörtgendir, en büyüğüdür. Burada her çubuk dolgundur, su her çubuğun üstünde durur ve cevap tüm çubukların toplamıdır. İkisinde de iki işaretçi, aynı nedenle daha alçak tarafı hareket ettirir: sonucu zaten belirlenmiş olan taraf daha alçak taraftır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def trap(height):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
height = [0, 3, 1, 0, 2, 5, 1, 2]
Beklenen
7