CP #13 : Trapping Rain Water Problemi
Problem surada.
Cozum
Surasi belli ki, verilen liste icerisinde cukurlari tespit etmemiz gerekiyor. Ve bu cukurda biriken su miktarini hesaplayip toplayacagiz.
Ilk etapta benim aklima listedeki sayilarin artip azalmasina bakarak cukurlari tespit etmek vardi ancak pek basarili olmadi. Naive bir implementasyon olarak, her bir stunda, kendisinden once ve sonra gelen, ve bu stundan daha yuksek olan duvarlari bulsak, ve bu cukurdaku su miktarini hesaplamak yerine sadece bu stunda birikebilecek su miktarini hesaplasak, ve bu sekilde tum stunlari toplayarak gitsek, sonuca ulasiriz. O zaman soyle yapiyoruz:
1. Her stunu itere et
2. Her bir stun degerinden once gelen stunlardaki, bu stundan yuksek olan en yukske stunu bul
3. Stun degerinden sonra gelen ve bu stundan yuksek olan en yuksek stunu bul
4. ikinci ve ucuncu adimlarda cukurun iki tarafini bulmus olduk. Ancak su, bunlardan kisasi kadar birikebilecegi icin min islemi yap
5. Minimum duvari bulduktan sonra mevcut stun degerini bundan cikartarak orada toplanabilecek su miktarini hesapla.
def trap(self, height):
ret = 0
# tum stunlari kontrol ediyoruz
for i in range(len(height)):
# mevcut stundan once gelen degerler
before = height[:i]
# mevcut stundan sonra gelen degerler
after = height[i+1:]
# eger bu araliklar bos degilse
# yani ornek olarak ilk stundan once gelen bir stun yok
# ya da son stundan sonra gelen
# eger bu kontrolu yapmazsak, max(height[:i]) hata verebilir
if before and after:
max_before = max(before)
max_after = max(after)
# su birikebilmesi icin kendisinden once gelen en yuksek duvar,
# kendisinden buyuk olmalidir. benzer sekilde kendisinden sonra gelen en yuksek
# duvar da kendisinden yuksek olmalidir ki cukur olussun.
if max_before > height[i] and max_after > height[i]:
# bunlardan kisa olani kadar yuksek su birikebilir
min_wall = min(max_before, max_after)
# bu stunda bu kadar su birikebilir
ret += min_wall - height[i]
return ret
Analiz
Kabul etmek gerekir ki cok performanssiz bir cozum. Ornek olarka for loop icerisinde bir de range uzerinde max islemi yapiyoruz. Direk O(n2). Ancak bunu iyilestirebilecegimiz sinyalleri aslinda yukaridaki algoritma adimlarini siralarken gelmeye baslamistir. Nedir bu sinyaller?
Kabul etmek gerekir ki cok performanssiz bir cozum. Ornek olarka for loop icerisinde bir de range uzerinde max islemi yapiyoruz. Direk O(n2). Ancak bunu iyilestirebilecegimiz sinyalleri aslinda yukaridaki algoritma adimlarini siralarken gelmeye baslamistir. Nedir bu sinyaller?
Dedik ki, her bir stun icin kendisinden once ve sonra gelen en yuksek duvar degerlerini hesaplamamiz gerekiyor. Aslinda bu islemi one-pass ile bir seferde yapabilir ve daha sonra yine one-pass ile biriken su miktarlarini hesaplayabiliriz. Bu durumda O(n) bir cozum elde etmis oluruz.
O zaman ilk once her bir stun icin, kendinden once ve sonra gelen en yuksek duvarlari bulalim:
# bir index icin, o index'ten once gelen en yukske duvari tutacak bir array tanimliyoruz
# burada -Inf vermemizin sebebi, sinirlarda tanimli deger olmamasi aslinda
# yani ilk stun icin kendisinden once gelen bir duvar yok dolayisi ile bunu -Inf ile
# temsil edebiliriz. Ya da -1 bile olurdu sanirim. Ama -Inf daha havali.
left = [float("-Inf")] * len(height)
# benzer sekilde verilen bir i indexi icin,
# o indexten sonra gelen en yuksek duvari tutacak bur array tanimliyoruz
right = [float("-Inf")] * len(height)
# bu islemler ayni dongu icinde de yapilabilirdi ama
# ben sifir kontrolu ve len kontrolu yapmamak icin ayri yapmayi tercih ettim
# once sol taraf
for i in range(1, len(height)):
# indexin solundaki en yuksek duvar
# ya kendisinin de solundakinden once gelen en yuksek duvar (left[i-1)
# ya da yeni gordumuzu height[i-1] degerei olacaktir
left[i] = max(left[i-1], height[i-1])
# sag tarafi bulmak icin arrayi sondan basa dogru traverse ediyoruz
for i in range(len(height)-2, -1, -1):
right[i] = max(right[i+1], height[i+1])
# biriken sulari kolayca hesaplayabiliriz simdi
for i in range(len(height)):
if left[i] > height[i] and right[i] > height[i]:
min_wall = min(left[i], right[i])
ret += min_wall - height[i]
return ret
Evet bu sekilde leetcode'a gonderdigimde beklenildigi gibi ciddi bir performans artisi gozlemlendi. Ilk O(n2) cozum 1764 ms zaman alirken (direkten donmususz), bu O(n) cozum sadece 96 ms zaman aldi. Memory kullaniminda ise belirgin bir degisiklik olmadi.
Ikinci cozumde memory kompleksitesinin de lineer olduguna dikkat cekelim. Left ve right olmak uzere iki array tuttuk ama bunlarin toplami herzaman input size kadar olacaktir.
Diger problemde gorusmek uzere,
stay hungry, stay foolish, stay healthy :)
Yorumlar
Yorum Gönder