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

Trapping Rain Water

Problem (yeniden ifade)

Negatif olmayan yükseklikler verildiğinde, yağmurdan sonra ne kadar su tutulabileceğini hesapla. Su her indekste, solundaki ve sağındaki en yüksek çubukların daha alçak olanına kadar durur.

Sezgi

i indeksindeki su min(leftMax[i], rightMax[i]) - height[i] (negatifse 0). Her iki max dizisini O(n) bellekte önceden hesaplayabilirsin; aynı fikri two pointers ile online (O(1) bellek) veya monoton yığınla (O(n) bellek; zaten “sonraki daha yüksek duvar” diye düşünüyorsan doğal) hesaplayabilirsin.

Yaklaşımlar

Maksimumlarla two pointers

Doğrulanmadı

Zaman O(n)Alan O(1)

Fikir. Her iki uçtan yürürken leftMax / rightMax tut. Her zaman daha küçük mevcut yüksekliğe sahip tarafı ilerlet: o tarafın max’ı o indeksteki suyu sınırlayan duvardır.

Yürüyüş. [0,1,0,2,1,0,1,3,2,1,2,1]. Sol taraf daha alçakken su leftMax kullanır; sağ daha alçakken rightMax. Toplam dolum 6.

Trade-off. Optimal bellek. İki dizili DP’den baskı altında icat etmesi biraz daha zor, ama O(1) ekstra bellek istediklerinde mülakat altını.

Çözüm

export function trap(height: number[]): number {
  let lo = 0, hi = height.length - 1;
  let leftMax = 0, rightMax = 0, water = 0;
  while (lo <= hi) {
    if (height[lo]! <= height[hi]!) {
      if (height[lo]! >= leftMax) leftMax = height[lo]!;
      else water += leftMax - height[lo]!;
      lo++;
    } else {
      if (height[hi]! >= rightMax) rightMax = height[hi]!;
      else water += rightMax - height[hi]!;
      hi--;
    }
  }
  return water;
}

export function trap(height: number[]): number {
  let lo = 0, hi = height.length - 1;
  let leftMax = 0, rightMax = 0, water = 0;
  while (lo <= hi) {
    if (height[lo]! <= height[hi]!) {
      if (height[lo]! >= leftMax) leftMax = height[lo]!;
      else water += leftMax - height[lo]!;
      lo++;
    } else {
      if (height[hi]! >= rightMax) rightMax = height[hi]!;
      else water += rightMax - height[hi]!;
      hi--;
    }
  }
  return water;
}

Monoton yığın

Doğrulanmadı

Zaman O(n)Alan O(n)

Fikir. İndekslerin azalan yığınını tut. Daha yüksek bir çubuk gelince vadıyı pop et ve yeni çubuk ile yeni yığın tepesi arasında yatay bir katman tut: yükseklik = min(leftWall, rightWall), mid, genişlik = duvarlar arası boşluk.

Yürüyüş. Aynı dizi: her pop bir segment üzerinde bir su “katmanı” doldurur. Katmanların toplamı yine 6.

Trade-off. Net geometrik hikâye; O(n) yığın kullanır. Problem zaten next-greater / histogram kokuyorsa (ve monoton yığını biliyorsan) tercih et. Bellekte two pointers kazanır.

Çözüm

/** Monotonic decreasing stack of indices; pop to trap water between walls. */
export function trapStack(height: number[]): number {
  const st: number[] = [];
  let water = 0;
  for (let i = 0; i < height.length; i++) {
    while (st.length && height[i]! > height[st[st.length - 1]!]!) {
      const mid = st.pop()!;
      if (!st.length) break;
      const left = st[st.length - 1]!;
      const h = Math.min(height[left]!, height[i]!) - height[mid]!;
      const w = i - left - 1;
      water += h * w;
    }
    st.push(i);
  }
  return water;
}

/** Monotonic decreasing stack of indices; pop to trap water between walls. */
export function trapStack(height: number[]): number {
  const st: number[] = [];
  let water = 0;
  for (let i = 0; i < height.length; i++) {
    while (st.length && height[i]! > height[st[st.length - 1]!]!) {
      const mid = st.pop()!;
      if (!st.length) break;
      const left = st[st.length - 1]!;
      const h = Math.min(height[left]!, height[i]!) - height[mid]!;
      const w = i - left - 1;
      water += h * w;
    }
    st.push(i);
  }
  return water;
}

Şablon bağlantısı

Buradaki birincil pattern two pointers (karşıt uçlar). Yığın sürümü, largest rectangle / daily temperatures’ın monoton yığın next-greater kuzenidir.

Yaygın hatalar

Önce daha uzun tarafı ilerletmek (yanlış sınırlayan duvar).
Yükseklik mevcut taraf max’ına eşitken suyun 0 olduğunu unutmak.
Yığın sürümü: genişlik i - left - 1, i - mid değil.

Yansıma

90 saniyenin altında two pointers mı yığın mı seçtiğin hangi ipucu oldu?
Yanlış bir “yalnızca sola bak” değişmezini hangi girdi bozar?
min(leftMax, rightMax) formülünden O(1) two-pointer kuralını türetebilir misin?