Her tekliften sonra alış-satış farkı
Görev tanımı
Problem
Bir teklif panosu teklifleri ("buy", price) ya da ("sell", price) olarak alıyor. Bu panoda hiçbir şey işlem görmüyor, yani her teklif kalıyor. Her tekliften sonra farkı bildir: en düşük satış fiyatı eksi en yüksek alış fiyatı. Taraflardan birinde henüz teklif yoksa None bildir. Bildirimlerin listesini döndür.
Örnekler
Input: quotes = [("buy", 100), ("sell", 105), ("buy", 102), ("sell", 104), ("buy", 99)]
Output: [None, 5, 3, 2, 2]
Neden: en iyi alış 102'ye çıkıyor, en iyi satış 104'e iniyor; 99'daki düşük alış hiçbir şeyi değiştirmiyor
Input: quotes = [("sell", 50), ("sell", 40)]
Output: [None, None]
Neden: henüz kimse alış fiyatı vermedi
Input: quotes = [("buy", 12), ("sell", 10)]
Output: [None, -2]
Neden: edge case: burada hiçbir şey işlem görmüyor, bu yüzden kesişen bir pano basitçe negatif bir fark gösterir
İpuçları
0 / 3
Her tekliften sonra yalnız iki fiyat önemli: en yüksek alış ve en düşük satış. Her seferinde her teklifi yeniden taramak karesel.
Alış tarafının istendiğinde maksimumuna, satış tarafının da minimumuna ihtiyacı var; iki taraf da büyümeye devam ediyor. Taraf başına bir heap her cevabı sabit zamanda verir.
Alış fiyatlarını bir max-heap'e, satış fiyatlarını bir min-heap'e push et. Her tekliften sonra iki heap de boş değilse satış heap'inin tepesi eksi alış heap'inin tepesini, değilse None bildir.
- Hedef zaman
- O(n log n)
- Hedef alan
- O(n)
Çözüm
Pano, aralarında bir sınır olan iki yarıdır; iki heap kalıbının ele aldığı şekil de bu: alış tarafı için bir max-heap, böylece en yüksek alış tepededir; satış tarafı için bir min-heap, böylece en düşük satış tepededir. Her teklif kendi tarafına bir push'tur ve fark yalnız iki tepeyi okur. Python'un heapq'su bir min-heap'tir, bu yüzden alış fiyatları negatif olarak saklanır; bu da farkı iki tepenin toplamına çevirir. Her teklif O(log n) tutar; zaman O(n log n), alan O(n).
import heapq
def spreads(quotes):
bids, asks = [], [] # bids: max-heap of negated prices, asks: min-heap
reports = []
for side, price in quotes:
if side == "buy":
heapq.heappush(bids, -price)
else:
heapq.heappush(asks, price)
# lowest sell minus highest buy; bids are stored negated
reports.append(asks[0] + bids[0] if bids and asks else None)
return reports
print(spreads([("buy", 100), ("sell", 105), ("buy", 102), ("sell", 104), ("buy", 99)])) # -> [None, 5, 3, 2, 2]
print(spreads([("sell", 50), ("sell", 40)])) # -> [None, None]
print(spreads([("buy", 12), ("sell", 10)])) # -> [None, -2]Kodda değil de fikirde mi takıldın? Heap temelleri bunu anlatıyor.