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

Hardsweep-line

The Skyline Problem

Problem (yeniden ifade)

Binalar yerde [left, right, height] eksen-hizalı dikdörtgenler. Silüeti anahtar noktalar [x, height] olarak döndür: yükseklik değişen her x, soldan sağa, 0 yüksekliğiyle biterek.

Sezgi

Soldan sağa süpür. Her bina left’te giriş (yükseklik ekle) ve right’ta çıkış (kaldır). Silüet yalnızca max aktif yükseklik değişince yazar. Aynı x’te bağ-kırıcı: girişler çıkışlardan önce (biri biterken diğeri başlarsa 0’a düşülmesin), daha yüksek girişler önce.

Yaklaşımlar

Süpürme + aktif yükseklikler

Doğrulanmadı

Zaman O(n log n)Alan O(n)

Fikir. Olaylar (x, −h, id) başlangıç ve (x, +h, id) bitiş; sırala. Canlı küme + tembel silmeli max-heap, artı yer yüksekliği 0. x’teki tüm olaylardan sonra max ≠ son yazılan yükseklik ise [x, max] ekle.

Yürüyüş. [[2,9,10],[3,7,15]] → [2,10], [3,15], [7,10], [9,0].

Trade-off. Tembel heap silme mülakat sürümü. Gerçek multiset C#’ta daha temiz (SortedDictionary). Sıralama anahtarı örtüşme kuralı: aynı x’te start-before-end.

Çözüm

export function getSkyline(buildings: number[][]): number[][] {
  const events: [number, number, number][] = [];
  for (let i = 0; i < buildings.length; i++) {
    const [l, r, h] = buildings[i]!;
    events.push([l, -h, i]);
    events.push([r, h, i]);
  }
  events.sort((a, b) => a[0]! - b[0]! || a[1]! - b[1]! || a[2]! - b[2]!);
  const live = new Set<number>([-1]);
  const heap: [number, number][] = [[0, -1]];
  const res: number[][] = [];
  let i = 0;
  while (i < events.length) {
    const x = events[i]![0]!;
    while (i < events.length && events[i]![0] === x) {
      const h = events[i]![1]!;
      const id = events[i]![2]!;
      if (h < 0) {
        live.add(id);
        heap.push([h, id]);
      } else {
        live.delete(id);
      }
      i++;
    }
    heap.sort((a, b) => a[0]! - b[0]!);
    while (heap.length && !live.has(heap[0]![1]!)) heap.shift();
    const maxH = -heap[0]![0]!;
    if (!res.length || res[res.length - 1]![1] !== maxH) res.push([x, maxH]);
  }
  return res;
}

export function getSkyline(buildings: number[][]): number[][] {
  const events: [number, number, number][] = [];
  for (let i = 0; i < buildings.length; i++) {
    const [l, r, h] = buildings[i]!;
    events.push([l, -h, i]);
    events.push([r, h, i]);
  }
  events.sort((a, b) => a[0]! - b[0]! || a[1]! - b[1]! || a[2]! - b[2]!);
  const live = new Set<number>([-1]);
  const heap: [number, number][] = [[0, -1]];
  const res: number[][] = [];
  let i = 0;
  while (i < events.length) {
    const x = events[i]![0]!;
    while (i < events.length && events[i]![0] === x) {
      const h = events[i]![1]!;
      const id = events[i]![2]!;
      if (h < 0) {
        live.add(id);
        heap.push([h, id]);
      } else {
        live.delete(id);
      }
      i++;
    }
    heap.sort((a, b) => a[0]! - b[0]!);
    while (heap.length && !live.has(heap[0]![1]!)) heap.shift();
    const maxH = -heap[0]![0]!;
    if (!res.length || res[res.length - 1]![1] !== maxH) res.push([x, maxH]);
  }
  return res;
}

Şablon bağlantısı

Sweep Line’ın skyline şekli: giriş/çıkış olayları, aktif yükseklik kümesi, max değişince yaz. LC 253 aynı süpürme, yükseklik multiset yerine sayım.

Yansıma

Başlangıç olayı (x, −h), bitiş (x, +h). Aynı x’te başlangıç önce sıralanır. Önce bitiş işlenirse yükseklik yere düşüp sahte nokta üretir.
Canlı yüksekliklerin max’ı değişince [x, max] yaz. Zemin 0. Bitiş, o binayı canlı kümeden çıkarır.
Örtüşen çatılar max’ta birleşir. Bitişik aynı yükseklik ayrı nokta üretmez. Boş çizgi yok.