Leetcode 121 Best Time to Buy and Sell Stock

Soru

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Örnek 1

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Örnek 2

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Çözüm

• Bir dizi günlük hisse senedi fiyatları verildiğinde, en yüksek kârı elde etmek için hisse senedi alım ve satım zamanlarını belirlemenizi ister. Bu problemde, yalnızca bir işlem yapma şansınız var; yani bir kez satın alabilir ve bir kez satabilirsiniz. Amaç, verilen fiyat listesine dayanarak mümkün olan en yüksek kârı hesaplamaktır.
• Girdi: Günlük hisse senedi fiyatlarını içeren bir tam sayı dizisi prices.
• Çıktı: Elde edilebilecek maksimum kâr miktarı.
• Bu problem için en etkili yöntem, lineer zaman karmaşıklığına sahip bir algoritmadır. Her günün fiyatı için, o güne kadar gördüğünüz en düşük fiyatı ve o fiyatla o gün arasındaki potansiyel kârı takip edersiniz.
• Çalışma Mekanizması:
• Başlangıç Değerlerinin Belirlenmesi: min_price başlangıçta sonsuz olarak ayarlanır, max_profit ise 0 olarak başlar.
• Döngü ile İşlem: Her gün için fiyatlar dizisi döngüye alınır. Eğer mevcut fiyat, şimdiye kadar gördüğünüz en düşük fiyatdan düşükse, bu en düşük fiyatı güncellersiniz. Eğer mevcut fiyat ile en düşük fiyat arasındaki fark, şimdiye kadar hesaplanan maksimum kârdan fazlaysa, maksimum kârı bu farkla güncellersiniz.
• Maksimum Kârın Dönüşü: İşlemler tamamlandığında, hesaplanan maksimum kâr değeri döndürülür.

Code

class Solution:
    def maxProfit(self, prices):
        if not prices:
            return 0

        min_price = float('inf')
        max_profit = 0
        
        for price in prices:
            if price < min_price:
                min_price = price  # En düşük fiyatı güncelle
            elif price - min_price > max_profit:
                max_profit = price - min_price  # Maksimum kârı güncelle

        return max_profit

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(n), burada n fiyatlar dizisinin uzunluğudur. Dizi boyunca bir kez geçiş yapılır.
• Space complexity (Alan Karmaşıklığı) : O(1), herhangi bir ekstra alan kullanılmaz.