Container With Most Water
Sana negatif olmayan tam sayılardan oluşan bir height listesi veriliyor. i. çizgi, 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 ç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ı konumlarındaki satırların yükseklikleri
- Döndürürinteger
- iki çizginin tutabileceği en fazla su
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 çizgilerin yükseklikleri 7 ve 6'dır ve aralarında 6 birim mesafe vardır; bu nedenle 6 × 6 = 36 tutarlar. En yüksek iki çizgi olan 1. ve 5. konumlardaki 7'ler ise yalnızca 7 × 4 = 28 tutar ve en dıştaki çift 3 × 7 = 21 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, bu nedenle 4 alır.
Gönderirken +15 gizli test
Ek soru
Burada, seçtiğin iki çizgi arasındaki çizgiler yok sayılır. Her çizgi dolu bir çubuk olsaydı, hepsinin arasında ne kadar su birikirdi? Bunu da O(n) zamanda hesaplayabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
İki dış çizgiyle başla: en geniş kabı onlar oluşturur. Uçlardan herhangi birini içeri taşımak genişlikten bir birim kaybettirir. Bu kaybı iki çizgiden hangisi telafi edebilir?
Su miktarı daha 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; bu yüzden hiçbir zaman fayda sağlayamaz. Yalnızca daha kısa çizgiyi değiştirmek işe yarayabilir.
Her iki uçta da birer işaretçi tut. Aralarındaki su miktarını ölç ve en iyi değeri koru, ardından daha kısa çizginin bulunduğu işaretçiyi bir adım içeri taşı. İşaretçiler buluştuğunda dur.
Çözüm
Yaklaşık n²/2 çizgi çifti vardır; dolayısıyla 10^4 çizginin tümünü kontrol etmek 5 × 10^7 çarpım anlamına gelir. Çözüm, su miktarının yalnızca bir çiftteki daha kısa çizgiye bağlı olmasıdır: Bir çizginin oluşturabileceği en geniş kabın kısa kenarı olduğunu öğrendiğinizde, onu kullanan daha dar hiçbir kap daha iyi sonuç veremez. İki işaretçi, bu gerçeği her iki uçtan tek geçişe dönüştürür.
Her çifti kontrol et
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Her konteyner bir i < j konum çiftiyle tanımlanır. Su, kısa olan duvarı aşana kadar yükselir ve duvarların arasındaki taban j - i genişliğindedir; dolayısıyla çiftin tutabileceği miktar min(height[i], height[j]) × (j - i) olur. Her çifti deneyip en büyüğünü tutarsan, tanım gereği yanıtı bulmuş olursun.
İşin zor yanı, çiftlerin sayısıdır. n çizgi, n(n-1)/2 çift oluşturur: 10^4 çizgi için yaklaşık 5 × 10^7 çift vardır ve liste her iki katına çıktığında bu sayı dört katına çıkar. Derlenmiş bir dil bunu saniyenin çok küçük bir bölümünde tamamlar; ancak Python, Ruby veya R için bu işlem birçok saniye sürer ve n 10^5'e ulaştığında sayı herhangi bir dil için fazla hızlı büyür.
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ı tut.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 bestEn uzun satırlar önce
Sezgi
Bir kaba kısa kenarının tarafından bakın. i çizgisi kısa kenarsa, su miktarı height[i] ile mesafenin çarpımıdır ve eş çizgi en az onun kadar yüksek olan herhangi bir çizgi olabilir. Bu nedenle, i kısa kenarken oluşabilecek en iyi kapta, i en uzaktaki ve en az onun kadar yüksek çizgiyle eşleşir.
Bu eş çizgileri hızlıca bulmak için çizgileri en uzundan en kısaya sıralayın. i çizgisinin sırası geldiğinde, daha önce yerleştirilen her çizgi en az onun kadar yüksektir ve bunların en uzaktaki olanı ya yerleştirilen indekslerin en solu ya da en sağıdır. Bu iki indeksi, lo ve hi değişkenlerini takip edin; i çizgisinin tutabileceği en fazla su miktarı height[i] × max(i - lo, hi - i) olur. Yanıt, bu değerlerin en büyüğüdür; çünkü en iyi kap, kısa kenarı sırası geldiğinde hesaba katılır.
İlk örnekte, 1 ve 5 konumlarındaki iki 7 önce gelir ve 28 birim su tutar. Ardından 7. konumdaki 6 gelir; bu durumda lo = 1 ve hi = 5 olur ve 6 × 6 = 36 birim su tutar. Daha kısa hiçbir çizgi bunu geçemez. Eşit yükseklikteki çizgiler herhangi bir sırada gelebilir: İki eşit çizgiden hangisi ikinci gelirse, ilkini eş çizgi olarak görür.
Sıralama O(n log n), tarama ise O(n) maliyetlidir; bu yeterince hızlıdır. Yine de sıralama için O(n) belleğe ihtiyaç duyar ve sonraki yaklaşım hem sıralamayı hem de bellek kullanımını ortadan kaldırır.
Algoritma
- İndeksleri yüksekliğe göre, en uzundan başlayarak sırala.
lovehideğerlerini bu sıralamadaki ilk indekse,bestdeğerini ise 0'a ayarla.- Sonraki her
iindeksi 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ş kapsayıcıyla başla: left = 0 ve right = n-1; ardından ölç. Şimdi iki çizgiden biri elenebilir ve seçim zorunludur: daha kısa olanı çıkar. Diyelim ki height[left] ≤ height[right]. left çizgisini kullanan diğer tüm kapsayıcılar, onu right çizgisinden daha yakındaki bir çizgiyle eşleştirir; dolayısıyla daha dardır ve yükseklikleri yine en fazla height[left] olur. Hiçbiri ölçtüğün sudan daha fazlasını tutamaz; bu yüzden left çizgisinin işi bitmiştir ve left bir adım sağa ilerler. Daha uzun çizgiyi hareket ettirmek, yükseklik sınırını aynı tutup genişliği azaltacağından, sonuç ancak daha kötü olabilir. İki yükseklik eşitse iki çizginin de işi bitmiştir; ikisinden birini hareket ettirebilirsin.
Her adımda bir çizgi bir daha kullanılmamak üzere elenir; bu yüzden n-1 adımdan sonra işaretçiler buluşur. En iyi çift hiçbir zaman atlanmaz: iki çizgisinden biri ilk kez elendiğinde, o anda ölçülen kapsayıcı en az o kadar su tutar.
[3, 7, 2, 5, 4, 7, 3, 6] dizisinde 0 ve 7 konumları 3 × 7 = 21 tutar. 3 daha kısa olduğundan left 1'e ilerler. 1 ve 7 konumları 6 × 6 = 36 tutar; şimdi 6 daha kısa olduğundan right 6'ya ilerler. Sonraki kapsayıcılar 15, 28, 12, 10 ve 2 tutar; dolayısıyla cevap 36 olarak kalır.
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 sakla.height[left] < height[right]iseleftdeğerini sağa doğru bir adım ilerlet. Aksi hâlderightdeğerini sola doğru bir adım 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
İki işaretçili döngü kısadır; bu yüzden hatalar ayrıntılarda gizlidir.
- Daha uzun çizgiyi hareket ettirmek. İlk örnekte sonuç 36 yerine 21 olur: 7. konumdaki 6, ilk çiftin daha uzun çizgisidir; bu nedenle 1. konumdaki 7 ile hiç karşılaşamadan ayrılır.
- Yükseklik olarak daha uzun çizgiyi veya iki çizginin ortalamasını kullanmak. Su daha kısa duvardan taşar, bu nedenle yükseklik minimum değerdir.
- Genişlikte bir eksik/fazla hatası.
ivejkonumlarındaki çizgiler arasındaj - imesafe vardır,j - i + 1değil; bu nedenle yan yana iki çizgi, kısa olanın yüksekliğini 1 ile çarparak su tutar. - Cevabın en uzun çizgiyi veya en dıştaki çifti kullandığını varsaymak. İlk örnekte iki 7, 28 su tutar ve en dıştaki çift 21 tutar; oysa cevap 36'dır.
- Daha büyük sınır değerlerinde taşma. Burada su miktarı 10^8'in altında kalır; ancak yükseklikler ve uzunluklar 10^5'e yakın olduğunda çarpım 2^31'i aşar ve 64 bitlik bir tamsayı gerekir.
Sıkça sorulan sorular4
Container With Most Water'ın zaman karmaşıklığı nedir?
İki işaretçili çözüm O(n) zamanda ve O(1) ek alan kullanarak çalışır. Her adımda bir işaretçi bir konum içeri hareket eder, bu nedenle en fazla n-1 adım vardır. Her çifti kontrol etmek O(n²) zaman alır ve çizgileri yüksekliğe göre sıralamak O(n log n) zaman alır.
Kısa çizgideki işaretçiyi neden hareket ettirelim?
Su, daha kısa çizgiyle sınırlanır. Bu çizgiyi içeren diğer tüm kapların daha içte bir eşi vardır; bu nedenle daha dardır ve yine de kısa çizgiden daha yüksek değildir. Hiçbiri ölçtüğün kabı geçemez, bu yüzden cevabı kaybetmeden kısa çizgiyi eleyebilirsin.
En Çok Su İçeren Kap problemi açgözlü bir problem midir?
Evet. Her adım, daha kısa çizgiyi eleyerek geri alınmayan yerel bir seçim yapar. Bu seçim güvenlidir çünkü adımın elediği her kap, daha önce ö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.
En Çok Su İçeren Kap, Yağmur Suyu Biriktirme probleminden nasıl farklıdır?
Burada yalnızca seçilen iki çizgi önemlidir ve aralarındaki çizgiler göz ardı edilir; bu nedenle yanıt tek bir dikdörtgendir. Trapping Rain Water probleminde her çubuk katıdır ve su, her çubuğun üzerinde iki yanındaki en uzun çubuklardan kısa olanının yüksekliğine kadar birikir; bu nedenle yanıt tüm konumlar üzerinden alınan bir toplamdır. Her ikisinin de O(n) zamanlı iki işaretçili çözümleri vardır, ancak işaretçi kuralları ve topladığınız değerler farklıdır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def maxArea(height):
# Kodu buraya yazınDurum 1
Durum 2
Girdi
height = [3, 7, 2, 5, 4, 7, 3, 6]
Beklenen
36