𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝟱. 𝗚𝘂̈𝗻: 𝗛𝗶𝘀𝘀𝗲 𝗔𝗹ı𝗺 𝘃𝗲 𝗦𝗮𝘁ı𝗺 𝗶𝗰̧𝗶𝗻 𝗘𝗻 𝗜𝘆𝗶 𝗭𝗮𝗺𝗮𝗻

Leetcode 121, sizden bir hisseyi almak ve satmak için en iyi zamanı bulmanızı ister. Size bir fiyat dizisi verilir. Her bir indeks bir günü temsil eder. Değer ise o günkü maliyettir.

Hedef basittir. En yüksek kârı elde etmek için bir gün alıp gelecekteki bir günde satmaktır. Eğer kâr mümkün değilse 0 döndürün.

Problem Kısıtlamaları:

  • Dizi uzunluğu 100.000'e kadar.
  • Fiyatlar 10.000'e kadar.
  • Satış işlemi alıştan sonra yapılmalıdır.

Yaklaşım 1: Saf Yöntem (Brute Force)

Brute force yöntemi, her bir alış ve satış çiftini kontrol eder. Bu yöntem iki döngü kullanır.

  • Zaman Karmaşıklığı: O(n²)
  • Sorun: Çok yavaştır.

Eğer 1.000 gününüz varsa, 1.000.000 kontrol yaparsınız. Eğer 100.000 gününüz varsa, 10.000.000.000 kontrol yaparsınız. Bu durum Leetcode'da zaman aşımına (timeout) neden olur.

Yaklaşım 2: Optimize Edilmiş Yöntem (Tek Geçiş)

Bunu minPrice ve maxProfit adlı iki değişken kullanarak tek bir geçişte çözebilirsiniz.

  • Zaman Karmaşıklığı: O(n)
  • Alan Karmaşıklığı: O(1)

Nasıl çalışır:

  1. minPrice değerini Infinity (Sonsuz) olarak ayarlayın.
  2. maxProfit değerini 0 olarak ayarlayın.
  3. Her bir fiyat için döngü kurun.
  4. Eğer mevcut fiyat minPrice değerinden düşükse, minPrice değerini güncelleyin.
  5. Eğer mevcut fiyat eksi minPrice, maxProfit değerinden büyükse, maxProfit değerini güncelleyin.

[7, 1, 5, 3, 6, 4] fiyatları ile örnek izleme:

    1. Gün: Fiyat 7. minPrice 7 olur. maxProfit 0 kalır.
    1. Gün: Fiyat 1. minPrice 1 olur. maxProfit 0 kalır.
    1. Gün: Fiyat 5. 5 - 1 = 4. maxProfit 4 olur.
    1. Gün: Fiyat 3. 3 - 1 = 2. maxProfit 4 kalır.
    1. Gün: Fiyat 6. 6 - 1 = 5. maxProfit 5 olur.
    1. Gün: Fiyat 4. 4 - 1 = 3. maxProfit 5 kalır.

Sonuç: 5.

Optimize edilmiş versiyon kazanır çünkü her bir fiyata yalnızca bir kez bakar. Büyük veri setleri için ölçeklenebilirliği iyidir.

Kaynak: https://dev.to/afuji/leetcode-150-day-5-best-time-to-buy-and-sell-stock-naive-vs-optimized-4mk1