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

Hardmonotonic-stack

Largest Rectangle in Histogram

Problem (yeniden ifade)

Birim genişlikte, yükseklikleri heights[i] olan çubuklar. Histogramın içindeki en büyük dikdörtgenin alanını döndür.

Sezgi

Her çubuk için, onu en kısa çubuk olarak kullanan en geniş dikdörtgen, solda ve sağda ilk katı daha kısa çubuğa kadar uzanır. Monoton artan yığın bu sınırları çubuk başına amortize O(1)’de bulur.

Yaklaşımlar

Artan yığın + sentinel boşaltma

Doğrulanmadı

Zaman O(n)Alan O(n)

Fikir. Katı artan yükseklikli indeks yığını. Daha alçak bir çubuk gelince (veya sonda sanal yükseklik-0), pop et ve height * (right - left - 1) hesapla; burada right = i ve left yeni tepe (veya -1).

Yürüyüş. [2,1,5,6,2,3] → en büyüğü yükseklik 5 genişlik 2 = 10 (2-3 indekslerindeki çubuklar), genel cevap 10.

Trade-off. İki geçişli “soldaki/sağdaki en yakın daha küçük” diziler de O(n)’de çalışır ama daha fazla bellek ve kod kullanır. Kaba kuvvet O(n²).

Çözüm

export function largestRectangleArea(heights: number[]): number {
  const n = heights.length;
  const stack: number[] = []; // increasing heights by index
  let best = 0;
  for (let i = 0; i <= n; i++) {
    const h = i === n ? 0 : heights[i]!;
    while (stack.length && h < heights[stack[stack.length - 1]!]!) {
      const height = heights[stack.pop()!]!;
      const left = stack.length ? stack[stack.length - 1]! : -1;
      const width = i - left - 1;
      best = Math.max(best, height * width);
    }
    stack.push(i);
  }
  return best;
}

export function largestRectangleArea(heights: number[]): number {
  const n = heights.length;
  const stack: number[] = []; // increasing heights by index
  let best = 0;
  for (let i = 0; i <= n; i++) {
    const h = i === n ? 0 : heights[i]!;
    while (stack.length && h < heights[stack[stack.length - 1]!]!) {
      const height = heights[stack.pop()!]!;
      const left = stack.length ? stack[stack.length - 1]! : -1;
      const width = i - left - 1;
      best = Math.max(best, height * width);
    }
    stack.push(i);
  }
  return best;
}

Şablon bağlantısı

En yakın daha küçük sınırlar için monoton yığın (artan yığın). 496/503/739’daki next-greater (azalan yığın) ile karşılaştır.

Her çubukta genişlet

Doğrulanmadı

Zaman O(n²)Alan O(1)

Fikir. Her indeksi en kısa çubuk alarak, çubuklar en az o kadar uzunken sola/sağa genişlet; alan = h * genişlik.

Trade-off. Türetmesi kolay; büyük n için çok yavaş. Yığın sürümü O(n) yükseltmesidir.

Çözüm

/** O(n²): for each bar expand left/right while height >= h[i]. */
export function largestRectangleAreaBrute(heights: number[]): number {
  let best = 0;
  const n = heights.length;
  for (let i = 0; i < n; i++) {
    let lo = i, hi = i;
    while (lo > 0 && heights[lo - 1]! >= heights[i]!) lo--;
    while (hi + 1 < n && heights[hi + 1]! >= heights[i]!) hi++;
    best = Math.max(best, heights[i]! * (hi - lo + 1));
  }
  return best;
}

/** O(n²): for each bar expand left/right while height >= h[i]. */
export function largestRectangleAreaBrute(heights: number[]): number {
  let best = 0;
  const n = heights.length;
  for (let i = 0; i < n; i++) {
    let lo = i, hi = i;
    while (lo > 0 && heights[lo - 1]! >= heights[i]!) lo--;
    while (hi + 1 < n && heights[hi + 1]! >= heights[i]!) hi++;
    best = Math.max(best, heights[i]! * (hi - lo + 1));
  }
  return best;
}

Derinlemesine

Histogram çubukları bir silüet oluşturur. Her i çubuğu için, height[i]’yi en kısa çubuk olarak kullanan en büyük dikdörtgen soldaki önceki daha küçük çubuktan sağdaki sonraki daha küçüğe uzanır. İndekslerin monoton artan yığını bu sınırları tek geçişte bulur: i’yi pop ettiğinde yeni tepe önceki daha küçük, mevcut indeks sonraki daha küçüktür.

Alan = height[mid] * (right - left - 1). Sonda bir sentinel 0 çalıştır ki her çubuk pop edilsin.

Yansıma

Artan yığın bir çubuk daha kısayken kapanır. Genişlik i - left - 1 mi, tepedeki indeksten mi?
Başta ve sonda sentinel neden şart? Tek çubuk ve tamamen artan dizi.
Eşit yükseklikte < ile <= aynı dikdörtgeni ikiye böler mi, yoksa bir kez mi sayar?