En Çok Su İçeren Kap: LeetCode 11’in Detaylı Analizi

En Çok Su İçeren Kap: LeetCode 11’in Detaylı Analizi

LeetCode’un 11. sorusu olan “En Çok Su İçeren Kap” problemi, iki işaretçi tekniğinin güzel bir örneğini sergiliyor. Bu problemde, verilen bir yükseklik dizisiyle, en çok suyu tutabilecek kapları bulmamız gerekiyor. Öncelikle problemi daha detaylı inceleyelim, ardından çözüm algoritmasını ve kodlamasını adım adım ele alalım. Sonrasında ise performans analizi yaparak çözümün etkinliğini tartışacağız.

Problem Tanımı

Verilen bir height dizisi, n tane dikey çizginin yüksekliklerini temsil eder. Bu çizgiler x ekseni üzerinde eşit aralıklarla yer almaktadır. Herhangi iki çizgi ve x ekseni arasında bir kap oluşur. Hedefimiz, bu kaplar arasında en büyük alanı içereni bulmaktır. Alan, iki çizgi arasındaki mesafe ile daha kısa çizginin yüksekliğinin çarpımıyla hesaplanır. Örneğin, height = [1,8,6,2,5,4,8,3,7] için en büyük alan 49’dur.

Çözüm Algoritması: İki İşaretçi Tekniği

Bu problemi çözmek için en etkin yöntem, iki işaretçi tekniğini kullanmaktır. İki işaretçi, dizinin başlangıcı ve sonuna yerleştirilir. Her adımda, daha küçük yüksekliğe sahip işaretçi içeri doğru hareket ettirilir. Bunun nedeni, daha küçük yüksekliğin alan sınırlayıcısı olmasıdır. Daha büyük yüksekliği değiştirerek daha büyük bir alan elde etme olasılığımız daha yüksektir. Bu işlem, işaretçiler çakışana kadar devam eder. Her adımda hesaplanan alan, şimdiye kadar bulunan en büyük alan ile karşılaştırılır ve en büyük alan güncellenir.

Örneğin, height = [1,8,6,2,5,4,8,3,7] için:

1. Başlangıçta sol işaretçi 1’de, sağ işaretçi 7’dedir. Alan = min(1,7) * (7-1) = 6
2. Sol işaretçi hareket eder. Alan = min(8,7) * (7-1) = 42
3. Sağ işaretçi hareket eder. Alan = min(8,3) * (7-2) = 15
4. ve böyle devam eder…

Kod Uygulaması (Python)

def maxArea(height):
    max_area = 0
    left = 0
    right = len(height) - 1
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        max_area = max(max_area, area)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_area

Performans Analizi

İki işaretçi tekniği, bu problemi O(n) zaman karmaşıklığıyla çözer. Yani, dizi boyutu arttıkça çözüm süresi lineer olarak artar. Uzay karmaşıklığı ise O(1)'dir çünkü yalnızca sabit miktarda ek uzay kullanılır. Bu, oldukça verimli bir çözümdür.

Sonuç

LeetCode 11 problemi, iki işaretçi tekniğinin problem çözümünde ne kadar etkili olduğunu gösteren güzel bir örnektir. Bu teknik, doğru uygulandığında, karmaşık problemleri verimli bir şekilde çözmemizi sağlar. Umarım bu detaylı açıklama, problemi anlamanıza ve çözmenize yardımcı olmuştur. Daha fazla algoritma ve veri yapısı örneği için fatihsoysal.com adresini ziyaret edebilirsiniz.

Ayrıca, konu hakkında daha fazla bilgi edinmek için burayı inceleyebilirsiniz.

#Etiketler: LeetCode, Algoritma, Veri Yapıları, İki İşaretçi Tekniği, En Çok Su İçeren Kap, Problem Çözme, Python, Zaman Karmaşıklığı, Uzay Karmaşıklığı, Programlama