Container With Most Water
Negatif olmayan tam sayılardan oluşan bir height listesi alırsın. i çizgisi, i konumunda duran ve yüksekliği height[i] olan dikey bir duvardır. Herhangi iki çizgi zeminle birlikte bir kap oluşturur ve bu kap, kısa olan çizginin yüksekliği ile iki çizgi arasındaki mesafenin çarpımı kadar su tutar. Diğer çizgiler engel olmaz. Tek bir çizgi çiftinin tutabileceği en fazla su miktarını döndür.
Fonksiyon
- heightinteger-array
- 0, 1, 2 ve devamındaki konumlardaki çizgilerin yükseklikleri
- Döndürürinteger
- iki çizginin tutabileceği en fazla su miktarı
Kısıtlar
2 ≤ height.length ≤ 1040 ≤ height[i] ≤ 104- Yanıt en fazla 108 olduğundan 32 bitlik bir tamsayıya sığar.
Örnekler
- Girdi
- height = [3, 7, 2, 5, 4, 7, 3, 6]
- Çıktı
- 36
- Açıklama
- 1 ve 7. konumlardaki, yükseklikleri 7 ve 6 olan çizgiler arasında 6 birim vardır ve 6 × 6 = 36 su tutarlar. En uzun iki çizgi olan 1 ve 5. konumlardaki 7'ler ise yalnızca 7 × 4 = 28 su tutar.
- Girdi
- height = [4, 4]
- Çıktı
- 4
- Açıklama
- İki çizgi tam olarak bir kap oluşturur: yüksekliği 4 ve genişliği 1, yani 4 alır.
Ek soru
Burada, iki çizginizin arasındaki çizgiler yok sayılır. Her çizgi düz bir çubuk olsaydı, aralarında toplam ne kadar su birikirdi? Bunu O(n) zamanda da hesaplayabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
İki dış çizgiyle başlayın: en geniş kabı onlar oluşturur. Uçlardan birini içeri taşımak genişlikten bir birim eksiltir. Bu eksilmeyi iki çizgiden hangisi telafi edebilir?
Su miktarı kısa çizgiyle sınırlıdır. Daha uzun çizgiyi içeri taşımak bu sınırı korur ve genişliği azaltır; dolayısıyla bu, hiçbir zaman fayda sağlayamaz. Yalnızca kısa çizgiyi değiştirmek işe yarayabilir.
Her iki uçta da bir işaretçi tut. Aralarındaki suyu ölç ve en iyi değeri sakla, ardından daha kısa çizgideki işaretçiyi bir adım içeri taşı. İşaretçiler buluştuğunda dur.
Çözüm
Tüm n²/2 çiftleri kontrol etmek, 10^4 çizgi için 5 × 10^7 çarpım demektir. Su miktarı yalnızca bir çiftteki kısa çizgiye bağlıdır; bu nedenle bir çizgi, oluşturabileceği en geniş kabın kısa kenarı olduğunda, onu kullanan daha dar hiçbir kap daha iyi sonuç veremez. İki işaretçi bunu, iki uçtan başlayarak yapılan tek bir geçişe dönüştürür.
Her çifti kontrol et
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Bir i < j çifti min(height[i], height[j]) × (j - i) değerini verir: su daha kısa olan duvardan taşar ve taban j - i genişliğindedir. Her çifti dene ve en büyük değeri sakla.
n çizgi, n(n-1)/2 çift verir: 10^4 çizgi için yaklaşık 5 × 10^7 ve n her ikiye katlandığında bunun dört katı.
Algoritma
bestdeğerini 0 olarak ayarla.- Her
ive ondan sonraki herjiçinmin(height[i], height[j]) × (j - i)değerini hesapla. bestile bu değerden büyük olanı sakla.bestdeğerini döndür.
def maxArea(height):
n = len(height)
best = 0
for i in range(n):
for j in range(i + 1, n):
water = min(height[i], height[j]) * (j - i)
best = max(best, water)
return bestÖnce en yüksek satırlar
Sezgi
i çizgisi bir kabın kısa kenarıysa, eşleştiği çizgi en az onun kadar yüksek olan herhangi bir çizgi olabilir. Dolayısıyla böyle bir en iyi kap, onu en az onun kadar yüksek olan en uzaktaki çizgiyle eşleştirir.
Çizgileri en uzundan en kısaya doğru yerleştir. i çizgisinin sırası geldiğinde, yerleştirilmiş her çizgi en az onun kadar yüksektir ve en uzaktaki çizgi, yerleştirilmiş en soldaki ya da en sağdaki indekstedir: lo veya hi. Dolayısıyla i çizgisinin alanı en fazla height[i] × max(i - lo, hi - i) olur ve en iyi kap, kısa çizgisi sırası geldiğinde hesaba katılır. Eşit yükseklikteki iki çizgiden son yerleştirilen, ilkini eşleşebileceği bir çizgi olarak görür.
İlk örnekte, 1 ve 5 konumlarındaki 7’ler önce gelir ve alanları 28 olur. Ardından 7. konumdaki 6, lo = 1 değerini görür ve alanı 36 olur. Sıralama O(n log n) zaman ve O(n) bellek gerektirir.
Algoritma
- İndisleri yüksekliğe göre, en uzun olan ilk sırada olacak şekilde sırala.
lovehideğerlerini bu sıralamadaki ilk indise,bestdeğerini ise 0 olarak ayarla.- Sonraki her
iindisi içinheight[i]değerinii - lovehi - ideğerlerinden büyük olanla çarp ve en iyi değeri koru. lovehideğerlerinii'yi içerecek şekilde güncelle.bestdeğerini döndür.
def maxArea(height):
# Indices from the tallest line to the shortest.
order = sorted(range(len(height)), key=lambda i: height[i], reverse=True)
lo = hi = order[0] # leftmost and rightmost index among the lines placed so far
best = 0
for i in order[1:]:
# Every placed line is at least as tall as line i, so line i is the
# shorter side, and its best partner is the placed line farthest away.
best = max(best, height[i] * max(i - lo, hi - i))
lo = min(lo, i)
hi = max(hi, i)
return bestHer iki uçtan iki işaretçi
Sezgi
En geniş kaptan başla: left = 0 ve right = n-1; height[left] ≤ height[right] olduğunu varsay. left çizgisini kullanan diğer tüm kaplar, bu çizgiyi daha yakındaki bir çizgiyle eşleştirir; dolayısıyla daha dardır ve height[left] kadar yüksek ya da daha alçaktır. Hiçbiri ölçtüğün su miktarını geçemez; bu nedenle left çizgisi artık işini tamamlamıştır ve left bir adım sağa ilerler. Yükseklikler eşitse her iki çizgi de işini tamamlamıştır, bu yüzden ikisinden birini ilerletmek uygundur.
Her adımda bir çizgi devre dışı bırakılır, bu nedenle işaretçiler n-1 adım sonra buluşur. En iyi çift asla atlanmaz: iki çizgisinden ilki devre dışı bırakıldığında, o anda ölçülen kap en az aynı miktarda su içerir.
İlk örnekte, 0 ve 7 konumları 21 tutar ve 3 devre dışı bırakılır. 1 ve 7 konumları 36 tutar ve 6 devre dışı bırakılır. Kalanlar 15, 28, 12, 10 ve 2 tutar.
Algoritma
left = 0,right = n-1vebest = 0olarak ayarla.left < rightolduğu sürecemin(height[left], height[right]) × (right - left)değerini hesapla ve en iyi değeri koru.height[left] < height[right]iseleftdeğerini bir adım sağa ilerlet. Aksi takdirderightdeğerini bir adım sola ilerlet.- İşaretçiler buluştuğunda
bestdeğerini döndür.
def maxArea(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
water = min(height[left], height[right]) * (right - left)
best = max(best, water)
# The shorter line cannot do better with any line closer in, so drop it.
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
Tuzaklar ve uç durumlar
- Daha uzun olan çizgiyi hareket ettirmek. 36 yerine 21 döndüren ilk örnekte, 7. konumdaki 6, 1. konumdaki 7 ile hiç karşılaşmadan önce aradan çıkar.
- Daha uzun olan çizgiyi veya ikisinin ortalamasını yükseklik olarak kullanmak. Su, daha kısa duvardan taşar; bu nedenle yükseklik minimum değerdir.
- Genişliği
j - i + 1olarak ölçmek.ivejkonumlarındaki çizgiler arasındaj - ibirim mesafe vardır; dolayısıyla[4, 4]8 değil, 4 tutar. - Yanıtın en uzun çizgileri veya en dıştaki çifti kullandığını varsaymak. İlk örnekte iki 7, 28 tutar ve en dıştaki çift 21 tutar; yanıt ise 36'dır.
Sıkça sorulan sorular3
Container With Most Water algoritmasının zaman karmaşıklığı nedir?
İki işaretçili çözüm, her adımda işaretçilerden biri bir konum içeri doğru hareket ettiği için O(n) zamanda ve O(1) ek alan kullanarak çalışır. Her çifti kontrol etmek O(n²) sürer ve çizgileri yüksekliğe göre sıralamak O(n log n) sürer.
Daha kısa çizgideki işaretçiyi neden hareket ettirelim?
Suyu daha kısa çizgi sınırlar. Bu çizgiyi koruyan diğer her kabın, daha içerde bir eşi vardır; bu nedenle daha dar ve daha yüksek değildir. Hiçbiri ölçtüğün kabı geçemez, bu yüzden cevabı kaybetmeden daha kısa çizgiyi eleyebilirsin.
En Çok Su İçeren Kap problemi açgözlü bir problem midir?
Evet. Her adımda geri alınmayan yerel bir seçim yapılır: daha kısa çizgiyi ele. Bu seçim güvenlidir çünkü elenen her kap, ölçülmüş olanlardan daha iyi değildir; bu nedenle problem hem açgözlü algoritmalar hem de iki işaretçi başlığı altında sınıflandırılır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def maxArea(height):
# Kodu buraya yazınTest #1
Test #2
Argüman
height = [3, 7, 2, 5, 4, 7, 3, 6]
Beklenen Çıktı
36