Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumtwo-pointers

Container With Most Water

Problem (yeniden ifade)

Bir çizgi üzerinde yükseklik çubukları verilir. x-ekseni ile en çok su tutan konteyneri oluşturan iki çizgiyi seç. O maksimum alanı döndür.

Sezgi

Alan = min(h[l],h[r]) * (r-l). İki uçtan başlamak genişliği maksimize eder; iyileştirmenin tek yolu daha kısa çizgiyi içe kaydırıp daha yüksek bir yükseklik ummaktır.

Yaklaşımlar

İki uçtan two pointers

Tested only

Time O(n)Space O(1)

Fikir. left=0, right=n-1. Maks alanı izle. Daha kısa yükseklikteki işaretçiyi hareket ettir. left≥right olunca dur.

Yürüyüş. Yükseklikler [1,8,6,2,5,4,8,3,7]: başlangıç genişlik 8, alan min(1,7)*8=8; solu 8’e taşı, … sonunda en iyi=49.

Trade-off. Greedy doğruluk şuna dayanır: daha uzun çizgiyi hareket ettirmek min yüksekliği artıramaz ve yalnızca genişliği azaltır.

Solution

export function maxArea(height: number[]): number {
  let left = 0, right = height.length - 1, best = 0;
  while (left < right) {
    const h = Math.min(height[left]!, height[right]!);
    best = Math.max(best, h * (right - left));
    if (height[left]! < height[right]!) left++;
    else right--;
  }
  return best;
}

export function maxArea(height: number[]): number {
  let left = 0, right = height.length - 1, best = 0;
  while (left < right) {
    const h = Math.min(height[left]!, height[right]!);
    best = Math.max(best, h * (right - left));
    if (height[left]! < height[right]!) left++;
    else right--;
  }
  return best;
}

Tüm çiftleri dene

Tested only

Time O(n²)Space O(1)

Fikir. Her (i,j) için alanı hesapla.

Yürüyüş. İç içe döngüler; maksimumu tut.

Trade-off. Doğruluk bariz; daha büyük kısıtlarda başarısız olur.

Solution

export function maxAreaBrute(height: number[]): number {
  let best = 0;
  for (let i = 0; i < height.length; i++)
    for (let j = i + 1; j < height.length; j++)
      best = Math.max(best, Math.min(height[i]!, height[j]!) * (j - i));
  return best;
}

export function maxAreaBrute(height: number[]): number {
  let best = 0;
  for (let i = 0; i < height.length; i++)
    for (let j = i + 1; j < height.length; j++)
      best = Math.max(best, Math.min(height[i]!, height[j]!) * (j - i));
  return best;
}

Şablon bağlantısı

Karşıt-uç two pointers; yüksekliği sınırlayan tarafı hareket ettir.

Yansıma

Hangi pattern bunu 90 saniye içinde ele verdi?
Standart şablondan ne değişti?
Pencere/işaretçi mantığındaki dikkatsiz bir off-by-one’ı hangi girdi bozar?