İçeriğe geç

Her tekliften sonra alış-satış farkı

Kolay#two-heaps#max-heap#min-heap~15 dk

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

Hedef zaman
O(n log n)
Hedef alan
O(n)

Kodda değil de fikirde mi takıldın? Heap temelleri bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case