Best Time to Buy and Sell Stock
Bir prices listesi alırsın; burada prices[i], i. gündeki bir hisse senedinin fiyatıdır. Bir gün bir hisse satın alabilir ve daha sonraki bir gün satabilirsin. Elde edebileceğin en büyük kârı döndür; mümkün olan tüm işlemler zarar ettiriyorsa 0 döndür.
Fonksiyon
- pricesinteger-array
- hissenin her günkü fiyatı, sırayla
- Döndürürinteger
- tek bir alış ve daha sonraki bir satıştan elde edilen en yüksek kâr veya 0
Kısıtlar
1 ≤ prices.length ≤ 1050 ≤ prices[i] ≤ 104- En fazla bir işlem yaparsın ve satın aldığın günden daha sonraki bir günde satarsın.
Örnekler
- Girdi
- prices = [7, 2, 5, 9, 1, 4]
- Çıktı
- 7
- Açıklama
- 1. günde 2'den alıp 3. günde 9'dan satarak 7 kâr elde edin. En düşük fiyat olan 4. gündeki 1, 9'dan sonra geldiği için bundan sonraki en iyi satış yalnızca 3 kazandırır.
- Girdi
- prices = [9, 7, 4, 3, 1]
- Çıktı
- 0
- Açıklama
- Fiyat her gün düşüyor, bu nedenle her satış alış fiyatının altında olur. İşlem yapmazsın ve kâr 0'dır.
Ek soru
İstediğin kadar işlem yapabiliyor, ancak aynı anda en fazla bir hisse tutabiliyor olsaydın ne olurdu?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Satış her zaman satın alma işleminden sonra gelir. Bir satış günü seçin: Bu gün için en çok kârı hangi satın alma günü sağlar?
Belirli bir satış günü için en iyi alış günü, ondan önceki en ucuz gündür. İleri doğru ilerlerken bunu hatırlarsan, her seferinde o günü yeniden aramana gerek kalmaz.
Günleri sırayla ilerleyin ve iki sayı tutun: şimdiye kadarki en düşük fiyat ve şimdiye kadarki en yüksek kâr. Her gün, bugünkü fiyattan en düşük fiyatı çıkararak elde edilen değeri en yüksek kârla karşılaştırın, ardından en düşük fiyatı güncelleyin.
Çözüm
Satmadan önce satın almalısın; bu nedenle cevap, en yüksek fiyattan en düşük fiyatın çıkarılması değildir. Satış yapabileceğin her gün için en iyi alış, ondan önceki en ucuz gündür. İlerlerken bu en düşük fiyatı takip etmek, problemi tek geçişe dönüştürür.
Her alım ve satım çiftini dene
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Her işlem bir alış günü ve daha sonraki bir satış gününden oluşur; bu yüzden her ikiliyi deneyip en büyük farkı tut. En iyi kârı 0'dan başlatmak, işlem yapmama seçeneğini de kapsar. İzin verilen her işlem kontrol edilir, bu nedenle yanıt doğrudur.
n fiyat içeren bir listede yaklaşık n²/2 ikili vardır: 100.000 gün, yaklaşık 5 milyar çıkarma işlemi demektir.
Algoritma
bestdeğerini 0 olarak ayarla.- Her satın alma günü
buyiçin döngüye gir. - Her biri için, ondan sonraki her satış günü
selliçin döngüye gir. prices[sell]değerindenprices[buy]değerini çıkar ve sonuç daha büyüksebestiçine kaydet.bestdeğerini döndür.
def maxProfit(prices):
best = 0
n = len(prices)
for buy in range(n):
for sell in range(buy + 1, n):
best = max(best, prices[sell] - prices[buy])
return best
Şimdiye kadarki en düşük fiyatla tek geçiş
Sezgi
Satış günü i'yi sabitle. Alım için en iyi gün, i'ye kadar olan en ucuz gündür; dolayısıyla i gününde biten en iyi işlem, prices[i] ile şimdiye kadarki en düşük fiyat arasındaki farkı kazandırır. Her satış günü, en iyi alım günüyle eşleştirilir; bu kârların en büyüğü cevaptır. Yeni bir en düşük fiyat belirleyen bir günde kâr 0'dır; bu, işlem yapmamakla aynıdır.
Bu yöntem her fiyatı bir kez okur ve lowest ile best olmak üzere iki sayı tutar: O(n) zaman ve O(1) alan.
Algoritma
lowestdeğişkenini ilk fiyata,bestdeğişkenini 0'a ayarla.- Fiyatları sırayla gözden geçir.
- Geçerli fiyat
lowestdeğerinden düşükse, onu yenilowestyap. - Geçerli fiyattan
lowestdeğerini çıkar ve sonuç daha büyüksebestdeğişkenine kaydet. bestdeğerini döndür.
def maxProfit(prices):
lowest = prices[0]
best = 0
for price in prices:
if price < lowest:
lowest = price
elif price - lowest > best:
best = price - lowest
return best
Tuzaklar ve uç durumlar
- En yüksek fiyattan en düşük fiyatı çıkarıp sonucu döndürmek.
[7, 2, 5, 9, 1, 4]dizisinde sonuç 8 olur, ancak 1, 9'dan sonra gelir. Doğru cevap 7'dir. - Cevabın negatif olmasına izin vermek.
[9, 7, 4, 3, 1]dizisinde en iyi fark -1'dir;bestdeğerini ilk farkla değil, 0 ile başlatın. lowestdeğerini 0 ile başlatmak. Böylece her kâr fiyatın kendisine eşit olur ve[9, 7, 4, 3, 1]dizisi 9 döndürür. Bu değeri ilk fiyatla başlatın.
Sıkça sorulan sorular3
Best Time to Buy and Sell Stock algoritmasının zaman karmaşıklığı nedir?
Tek geçişli çözüm, n gün için O(n) zaman alır; çünkü her fiyatı bir kez okur ve O(1) ek alan kullanır: şimdiye kadarki en düşük fiyat ve en iyi kâr. Her gün çiftini denemek O(n²) zaman alır.
En düşük fiyatı en yüksek fiyattan neden çıkarmıyoruz?
En düşük fiyat en yüksek fiyattan sonra gelebilir ve satış yapmadan önce alış yapmalısın. [7, 2, 5, 9, 1, 4] dizisinde 1, 9'dan sonra gelir; bu nedenle izin verilen en iyi işlem 2'den alıp 9'dan satarak 7 kazandırır.
Best Time to Buy and Sell Stock, dinamik programlama problemi midir?
Bunu iki şekilde de yorumlayabilirsin. Şimdiye kadarki en düşük fiyat, her gün güncellediğin küçük bir durum bilgisidir; bu, dinamik programlama yaklaşımıdır. Her satışı daha önceki en ucuz günle eşleştirmek ise açgözlü yaklaşımdır. Her ikisi de aynı tek geçişli koda ulaşır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def maxProfit(prices):
# Kodu buraya yazınTest #1
Test #2
Argüman
prices = [7, 2, 5, 9, 1, 4]
Beklenen Çıktı
7