Son penceredeki istekler
Görev tanımı
Problem
Bir servis her isteğin geliş zamanını milisaniye cinsinden kaydediyor ve zamanlar azalmayan sırada geliyor. Her istek için son w milisaniye içinde, yani kendi zamanı eksi w'den büyük (eşit değil) bir zamanda kaç isteğin, kendisi dahil, geldiğini bildir. İstek başına bir sayı döndür.
Örnekler
Input: times = [0, 400, 900, 1000, 1400], w = 1000
Output: [1, 2, 3, 3, 3]
Neden: 1000'de 0 zamanındaki istek tam w yaşında ve artık sayılmıyor
Input: times = [5, 5, 5], w = 1
Output: [1, 2, 3]
Neden: eşit zamanların hepsi aynı pencereye düşüyor
Input: times = [], w = 50
Output: []
Neden: edge case: istek yok
İpuçları
0 / 3
Bir istek bir geliş için fazla eskiyse sonraki her geliş için de fazla eskidir, çünkü zamanlar hiç azalmaz.
Eski istekler önden çıkar, yeniler arkaya katılır; bu tam olarak ilk giren ilk çıkar.
Zamanlardan oluşan bir kuyruk tut. Her geliş için zamanını arkaya ekle, sonra öndeki zaman en fazla geliş zamanı eksi w olduğu sürece önden zamanları çıkar. Kuyruk uzunluğu o gelişin cevabıdır.
- Hedef zaman
- O(n)
- Hedef alan
- O(n)
Kısıtlar
- times are in non-decreasing order
Çözüm
Zamanlar hiç azalmadığı için istekler geldikleri sırayla süresini doldurur; bu yüzden hâlâ pencerenin içindeki istekler her zaman bir kuyruğun önünde bir blok oluşturur. Her geliş arkaya katılır, süresi dolan zamanlar da kalan en eskisi yeterince yeni olana kadar önden çıkar. Her zaman bir kez eklenir ve en fazla bir kez çıkarılır; bu yüzden tek bir geliş birçoğunu çıkarsa bile toplam iş doğrusaldır. Zaman O(n), alan O(n); bu üst sınıra her istek tek bir pencereye düştüğünde ulaşılır.
from collections import deque
def recent_counts(times, w):
window, out = deque(), []
for t in times:
window.append(t)
while window[0] <= t - w: # too old now, and for every later arrival
window.popleft()
out.append(len(window))
return out
print(recent_counts([0, 400, 900, 1000, 1400], 1000)) # -> [1, 2, 3, 3, 3]
print(recent_counts([5, 5, 5], 1)) # -> [1, 2, 3]
print(recent_counts([], 50)) # -> []Kodda değil de fikirde mi takıldın? Kuyruk temelleri bunu anlatıyor.