Stock Span Problem
Her gün için bir hisse senedinin kapanış fiyatı verilir: prices[i], i. gündeki fiyattır. i. günün aralığı, fiyatın prices[i] değerinden küçük veya ona eşit olduğu ve i. günle biten, bu gün de sayılarak art arda gelen günlerin sayısıdır.
Her günün aralığını, prices ile aynı sırada döndürün. Her aralık en az 1'dir, çünkü bir gün her zaman kendisini sayar.
Fonksiyon
- pricesinteger-array
- her günkü fiyat, sırayla
- Döndürürinteger-array
- her günün zaman aralığı, aynı sırayla
Kısıtlar
1 ≤ prices.length ≤ 1041 ≤ prices[i] ≤ 105- Aynı fiyata sahip daha önceki bir gün aralığa dahil edilir; aralığı yalnızca kesinlikle daha yüksek bir fiyat durdurur.
Örnekler
- Girdi
- prices = [31, 27, 14, 21, 30, 18, 40]
- Çıktı
- [1, 1, 1, 2, 4, 1, 7]
- Açıklama
- 21’deki 3. gün, 14’ün üzerinden geriye uzanır ve 27’de durur: aralık 2. 30’daki 4. gün, 31’de durur: aralık 4. 40’taki 6. gün, önceki tüm fiyatların üzerine çıkar ve 7 günün tamamını kapsar.
- Girdi
- prices = [8, 8, 3, 8]
- Çıktı
- [1, 2, 1, 4]
- Açıklama
- Eşit fiyatlar da sayılır; bu yüzden 8 fiyatındaki 1. gün, 0. günü kapsar ve 2 alır. 8 fiyatındaki 3. gün, 3. günü ve önceki iki 8'i kapsar; aralık 4'tür.
- Girdi
- prices = [50, 40, 30, 20]
- Çıktı
- [1, 1, 1, 1]
- Açıklama
- Her gün bir önceki günden daha ucuzdur; bu nedenle hiçbir aralık günün kendisinden daha geriye uzanmaz ve her aralık 1'dir.
Ek soru
Fiyatlar artık teker teker geliyor ve her biri geldiğinde ilgili aralığı bildirmen gerekiyor. Hangi yaklaşım hâlâ işe yarıyor ve çağrılar arasında neyi saklıyor?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Her günden geriye doğru saymak işi tekrarlar: aynı fiyattan 8000 gün boyunca, yalnızca son gün 8000 gün geriye gider. Bugünden geriye doğru giderken, hangi önceki günleri bir daha hiç hesaba katmayabilirsin?
Bugünkü fiyat önceki bir günün fiyatı kadar ya da ondan daha yüksek olduğunda, o önceki gün daha sonraki bir aralığı durduran gün olamaz: bugünkü gün daha yakındır ve en az onun kadar pahalıdır. Yalnızca kendilerinden sonraki tüm günlerden daha pahalı olan günler önemini korur ve bu günlerin fiyatları en eskiden en yeniye doğru düşer.
Günleri sırayla ilerle ve hâlâ önemli olan önceki günleri indeks olarak bir yığında tut. Bugün için yanıt vermeden önce, fiyatı bugünün fiyatından küçük veya ona eşit olan tüm günleri yığından çıkar. Yığının boş olması, aralığın 0. güne kadar uzandığı anlamına gelir; aksi hâlde, yığının tepesinde kalan günden bir gün sonrasında durur. Ardından bugünü yığına ekle.
Çözüm
Bir günün aralığı, fiyatı kesinlikle daha yüksek olan en yakın önceki günde sona erer. Bu günü bulmak için geriye doğru ilerlemek, gün başına en fazla n adım gerektirir. Bunun yerine, gelecekteki bir aralığı hâlâ durdurabilecek günleri tut: fiyatları kesinlikle azalan indekslerden oluşan bir yığın, tek geçişte tüm sınırları bulur.
Her günden geriye doğru say
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Tanımı izleyin. i günü için, oradaki fiyat prices[i] değerinden küçük veya ona eşit olduğu sürece her seferinde bir gün geriye gidin ve i gününü de sayın. İlk kesin olarak daha yüksek fiyat veya dizinin başlangıcı bu yürüyüşü bitirir.
Hiçbir yürüyüş daha önceki bir yürüyüşü yeniden kullanmaz. Fiyatlar sabit ya da yükseliyorsa her yürüyüş 0. güne kadar gider: n = 10^4 gün yaklaşık 5 × 10^7 adım demektir.
Algoritma
spanadında,pricesdizisiyle aynı uzunlukta bir dizi oluşturun.- Her
igünü için bir sayaç değerini 0 olarak ayarlayın vejişaretçisiniiolarak belirleyin. j ≥ 0veprices[j] ≤ prices[i]olduğu sürece sayacı 1 artırın vejdeğerini bir gün geriye alın.- Sayaç değerini
span[i]içine kaydedin. Son günden sonraspandeğerini döndürün.
def stockSpan(prices):
span = []
for i in range(len(prices)):
count = 0
j = i
# Count today and every earlier day in a row that is not more expensive.
while j >= 0 and prices[j] <= prices[i]:
count += 1
j -= 1
span.append(count)
return spanDaha yüksek günlerden oluşan monotonik yığın
Sezgi
Kesin olarak daha yüksek fiyata sahip en yakın önceki güne engelleyici denir. Aralık today - blocker olur; böyle biri yoksa today + 1 olur.
İlk örnekte 3. günün fiyatı 21, 4. günün fiyatı 30'dur. Daha sonraki her yürüyüş önce 4. güne ulaşır ve 30'u aşan herhangi bir fiyat 21'i de aşacağından, 3. gün artık hiçbir zaman engelleyici olamaz. Genel olarak, bugün geldiğinde fiyatı bugünkü fiyata eşit veya daha düşük olan önceki tüm adayların işi bitmiştir: onları yığından çıkar. Üstte kalan gün bugünün engelleyicisidir. Ardından bugünü yığına ekle.
Yığındaki fiyatlar alttan üste doğru kesin olarak azalır; bu nedenle kalan ilk fiyat, en yakın yüksek fiyattır. İlk örnekte 4. gün, 3. ve 1. günleri yığından çıkarır ve 0. günde durur; aralık 4 - 0 = 4 olur. Her gün yığına bir kez eklenir ve en fazla bir kez çıkarılır, dolayısıyla bu geçiş O(n) sürede çalışır.
Algoritma
spandizisini ve gün indeksleri için boş bir yığın oluşturun.- Her
todaygünü için, fiyatıprices[today]değerine eşit veya bundan düşük olan indeksleri yığından çıkarın. - Yığın boşsa aralık
today + 1olur; değilse aralıktodayile en üstteki indeksin farkıdır. todaydeğerini yığına ekleyin ve sonraki güne geçin.spandeğerini döndürün.
def stockSpan(prices):
span = [0] * len(prices)
higher = [] # indices of earlier days, prices strictly falling toward the top
for today, price in enumerate(prices):
# A day that is not more expensive than today can never stop a later span.
while higher and prices[higher[-1]] <= price:
higher.pop()
# The span reaches back to the nearest more expensive day, or to day 0.
span[today] = today - higher[-1] if higher else today + 1
higher.append(today)
return span
Tuzaklar ve uç durumlar
<=yerine<için elemanları yığından çıkarmak.[8, 8, 3, 8]dizisinde son günün aralığı 4'tür; önceki 8'de durmak aralığı 2 yapar.- Yığın boş olduğunda
today + 1yerinetodayyazmak. 0. gün 0 değil, 1 almalıdır. - Her gün için yalnızca bir kez eleman çıkarmak. İlk örnekte 40'ın 5., 4. ve 0. günleri geçmesi gerekir. 5. günden sonra durursanız 4. gün engelleyiciymiş gibi görünür ve aralık 7 yerine 2 olur.
- Lua ve R'de diziler 1'den başlar. 1 tabanlı indekslerde, yığın boşsa aralık
todayolur;today + 1değil.
Sıkça sorulan sorular4
Hisse senedi aralığı probleminin zaman karmaşıklığı nedir?
Monotonik yığınla O(n) zaman ve O(n) ek alan gerekir; çünkü bir gün yığından en fazla bir kez çıkar. Fiyatlar sürekli yükselirken veya sabit kalırken her günden geriye doğru ilerlemek O(n²) zaman alır.
Yığın fiyatları mı yoksa gün indekslerini mi saklamalı?
Gün indisleri. Aralık, gün sayısıdır ve bunu yalnızca engelleyicinin indisi verir. prices[index] karşılaştırma için fiyatı okur.
Hisse senedi aralığı problemi ayrı bir yığın kullanılmadan çözülebilir mi?
Evet. j = today - 1 noktasından başla; j ≥ 0 ve prices[j] ≤ prices[today] olduğu sürece j - span[j] noktasına atla; çünkü bu aralıktaki her günün fiyatı en fazla prices[j] değerindedir. Aralık today - j olur. Atlamalar yalnızca yığının tutacağı günlere ulaşır, bu nedenle geçiş O(n) sürer.
Hisse senedi aralığı problemi, önceki daha büyük eleman problemi midir?
Evet, gün cinsinden ölçülür: Her gün için, fiyatı kesin olarak daha yüksek olan en yakın önceki günü bulur ve kaç gün geriye gittiğini bildirirsin. Tarama yönünü veya karşılaştırmayı değiştirirsen aynı yığın; sonraki daha büyük, sonraki daha küçük ya da önceki daha küçük değeri verir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def stockSpan(prices):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
prices = [31, 27, 14, 21, 30, 18, 40]
Beklenen Çıktı
[1, 1, 1, 2, 4, 1, 7]