Leetcode 11 Container With Most Water

Soru

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Örnek 1

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Örnek 2

Input: height = [1,1]
Output: 1

Çözüm

• Verilen bir yükseklik listesiyle en fazla suyu tutabilecek iki çizgiyi bulmanızı isteyen bir problem. Bu problemde amaç, iki çizgi arasındaki maksimum su miktarını tutan alanı hesaplamaktır. Çizgilerin konumları listelenmiş ve bunların arasındaki su hacmi, çizgilerin yüksekliği ve aralarındaki mesafe ile belirlenir.
• Bu problem genellikle “two-pointer” tekniği kullanılarak çözülür. Burada, iki işaretçi (pointer) dizinin başında ve sonunda başlar ve su tutma kapasitesini maksimize edecek şekilde içe doğru hareket ederler.
• Çalışma Mekanizması:
• İşaretçilerin İnitialize Edilmesi: left işaretçisi dizinin başında, right işaretçisi ise dizinin sonunda başlar.
• Su Kapasitesinin Hesaplanması: İki çizgi arasındaki genişlik (width) ve iki çizgi arasındaki minimum yükseklik (water_height) kullanılarak mevcut su kapasitesi hesaplanır.
• Maksimum Su Kapasitesinin Güncellenmesi: Şu ana kadar hesaplanan maksimum su kapasitesi (max_water) ile mevcut kapasite karşılaştırılır ve daha büyük olanı kaydedilir.
• İşaretçilerin Hareketi: En düşük çizgiye sahip tarafın işaretçisi bir adım içe doğru hareket eder, böylece potansiyel olarak daha yüksek bir çizgi ile daha büyük bir alan hesaplaması yapılır.
• Sonuç Döndürme: İşaretçiler birbiriyle kesişene kadar bu işlem tekrarlanır ve hesaplanan maksimum su kapasitesi döndürülür.

Code

class Solution:
    def maxArea(self, height):
        left, right = 0, len(height) - 1
        max_water = 0
        while left < right:
            # İki çizgi arasındaki mesafeyi ve en düşük çizgiyi kullanarak su kapasitesini hesapla
            width = right - left
            water_height = min(height[left], height[right])
            max_water = max(max_water, water_height * width)
            
            # Su tutma kapasitesini artırmak için daha düşük yükseklikteki çizgiyi hareket ettir
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return max_water
        

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(n), burada n dizinin uzunluğudur. Her eleman yalnızca bir kez işaretçiler tarafından incelenir.
• Space complexity (Alan Karmaşıklığı) : O(1), çünkü ekstra bir alan kullanılmaz ve yalnızca iki işaretçi ile çözüm sağlanır.