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

Easyqueue-deque

Moving Average from Data Stream

Problem (yeniden ifade)

Pencere boyutu verildiğinde, next(val) ile tamsayı akışı. En fazla son size değerin ortalamasını döndür.

Sezgi

Kuyruk pencereyi tutar; çalışan toplamı koru; dolunca en eskisini düş.

Yaklaşımlar

Sabit boyutlu pencere kuyruğu

Doğrulanmadı

Zaman O(1) nextAlan O(size)

Fikir. val’ı kuyruğa al, toplama ekle; count > size ise dequeue edip çıkar; sum/count döndür.

Adım adım. size=3: 1 → 1; 10 → 5.5; 3 → 4.666…; 5 → 6.

Trade-off’lar. Dairesel tampon bazı dillerde kaydırma maliyetini önler.

Çözüm

export class MovingAverage {
  private size: number;
  private q: number[] = [];
  private sum = 0;
  constructor(size: number) {
    this.size = size;
  }
  next(val: number): number {
    this.q.push(val);
    this.sum += val;
    if (this.q.length > this.size) this.sum -= this.q.shift()!;
    return this.sum / this.q.length;
  }
}

export class MovingAverage {
  private size: number;
  private q: number[] = [];
  private sum = 0;
  constructor(size: number) {
    this.size = size;
  }
  next(val: number): number {
    this.q.push(val);
    this.sum += val;
    if (this.q.length > this.size) this.sum -= this.q.shift()!;
    return this.sum / this.q.length;
  }
}

Şablon bağlantısı

Kuyruk / deque kayan pencere toplulaştırma.

Yansıma

Pencere dolunca soldan çık ve toplamdan düş. Bölen size mı, görülen sayı mı?
İlk çağrılar pencereden kısadır. Böleni size yaparsan ortalama küçülür.
Negatif değerler toplamda kalır. Tam sayı bölme yok.