Best Time to Buy and Sell Stock
لديك قائمة prices، حيث يمثّل prices[i] سعر سهم واحد في اليوم i. يمكنك شراء سهم واحد في يوم ما وبيعه في يوم لاحق. أعد أكبر ربح يمكنك تحقيقه، أو 0 إذا كانت كل صفقة ممكنة تؤدي إلى خسارة.
الدالة
- pricesinteger-array
- سعر السهم في كل يوم، بالترتيب
- تُرجعinteger
- أكبر ربح من عملية شراء واحدة ثم بيع لاحق، أو 0
القيود
1 ≤ prices.length ≤ 1050 ≤ prices[i] ≤ 104- يمكنك إجراء صفقة واحدة كحد أقصى، ويجب أن تبيع في يوم لاحق ليوم الشراء.
أمثلة
- المدخلات
- prices = [7, 2, 5, 9, 1, 4]
- المخرجات
- 7
- الشرح
- اشترِ في اليوم 1 بسعر 2، وبِع في اليوم 3 بسعر 9 لتحقق ربحًا قدره 7. يأتي أقل سعر، وهو 1 في اليوم 4، بعد السعر 9، لذا فإن أفضل عملية بيع بعده تحقق ربحًا قدره 3 فقط.
- المدخلات
- prices = [9, 7, 4, 3, 1]
- المخرجات
- 0
- الشرح
- ينخفض السعر كل يوم، لذا ستكون كل عملية بيع بسعر أقل من سعر الشراء. لا تُجري أي تداول، ويكون الربح 0.
سؤال إضافي
ماذا لو كان بإمكانك إجراء أي عدد تريده من عمليات التداول، مع الاحتفاظ بسهم واحد كحد أقصى في كل مرة؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
يأتي البيع دائمًا بعد الشراء. اختر يومًا للبيع: أي يوم للشراء يحقق أكبر ربح له؟
في يوم بيع معيّن، أفضل يوم للشراء هو أرخص يوم يسبقه. لا تحتاج إلى البحث عن ذلك اليوم مجددًا في كل مرة إذا تذكّرته وأنت تتقدّم.
تتبّع الأيام بالترتيب واحتفظ برقمين: أدنى سعر حتى الآن وأفضل ربح حتى الآن. في كل يوم، قارن سعر اليوم مطروحًا منه أدنى سعر بأفضل ربح، ثم حدّث أدنى سعر.
الحل
يجب أن تشتري قبل أن تبيع، لذا فالإجابة ليست أعلى سعر ناقص أدنى سعر. في كل يوم يمكنك فيه البيع، يكون أفضل شراء هو في اليوم الأقل سعرًا قبله. إن الاحتفاظ بأقل سعر مع التقدم يومًا بعد يوم يحوّل المسألة إلى مرور واحد.
جرّب كل زوج من عمليات الشراء والبيع
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
كل عملية تداول تتكوّن من يوم شراء ويوم بيع لاحق، لذا جرّب كل زوج واحتفظ بأكبر فرق. إن بدء أفضل ربح عند 0 يغطي خيار عدم التداول. تُفحَص كل عملية تداول مسموح بها، لذا تكون الإجابة صحيحة.
تتضمن قائمة من n سعرًا نحو n²/2 من الأزواج: 100,000 يوم تعني نحو 5 مليارات عملية طرح.
الخوارزمية
- عيّن
bestإلى 0. - كرّر على كل يوم شراء
buy. - لكل يوم منها، كرّر على كل يوم بيع
sellيأتي بعده. - احسب
prices[sell]ناقصprices[buy]، وخزّنه فيbestإذا كان أكبر. - أعِد
best.
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
تمريرة واحدة مع أقل سعر حتى الآن
الفكرة
ثبّت يوم البيع i. أفضل يوم للشراء هو أرخص يوم حتى اليوم i، لذا فإن أفضل صفقة تنتهي في اليوم i تحقق ربحًا يساوي prices[i] مطروحًا منه أقل سعر حتى الآن. يُقرَن كل يوم بيع بأفضل يوم شراء له، لذا فإن أكبر هذه الأرباح هو الجواب. في اليوم الذي يسجّل فيه السعر انخفاضًا جديدًا، يكون الربح 0، وهو مثل عدم التداول.
يمرّ التكرار على كل سعر مرة واحدة ويحتفظ برقمين، lowest وbest: زمن O(n) ومساحة O(1).
الخوارزمية
- اضبط
lowestعلى السعر الأول وbestعلى 0. - مرّ على الأسعار بالترتيب.
- إذا كان السعر الحالي أقل من
lowest، فاجعله قيمةlowestالجديدة. - احسب السعر الحالي ناقص
lowest، وخزّنه فيbestإذا كان أكبر. - أعِد
best.
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
أخطاء شائعة وحالات حدّية
- إرجاع أعلى سعر ناقص أدنى سعر. في
[7, 2, 5, 9, 1, 4]تكون النتيجة 8، لكن القيمة 1 تأتي بعد القيمة 9. الإجابة هي 7. - السماح بأن تصبح الإجابة سالبة. في
[9, 7, 4, 3, 1]يكون أفضل فرق هو -1؛ ابدأbestبالقيمة 0، وليس بالفرق الأول. - بدء
lowestبالقيمة 0. عندئذٍ يكون كل ربح مساويًا للسعر نفسه، لذا تعيد[9, 7, 4, 3, 1]القيمة 9. ابدأ بالسعر الأول.
أسئلة شائعة3
ما التعقيد الزمني لمسألة أفضل وقت لشراء الأسهم وبيعها؟
يستغرق الحل بتمرير واحد زمنًا قدره O(n) لمدة n يومًا، لأنه يقرأ كل سعر مرة واحدة، ويستخدم مساحة إضافية قدرها O(1): أقل سعر حتى الآن وأفضل ربح. أما تجربة كل زوج من الأيام فتستغرق زمنًا قدره O(n²).
لماذا لا نطرح أدنى سعر من أعلى سعر؟
قد يأتي أقل سعر بعد أعلى سعر، ويجب عليك الشراء قبل البيع. في [7, 2, 5, 9, 1, 4] يأتي 1 بعد 9، لذا فإن أفضل صفقة مسموح بها هي الشراء بسعر 2 والبيع بسعر 9 لتحقيق ربح قدره 7.
هل تُعدّ مسألة أفضل وقت لشراء الأسهم وبيعها مسألة برمجة ديناميكية؟
يمكنك قراءتها بأيٍّ من الطريقتين. أقل سعر حتى الآن هو حالة صغيرة تحدّثها كل يوم، وهذا هو منظور البرمجة الديناميكية. أمّا ربط كل عملية بيع بأرخص يوم سابق فهو المنظور الجشع. وكلاهما يؤدي إلى الشيفرة نفسها ذات المرور الواحد.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def maxProfit(prices):
# اكتب الكود هنااختبار #1
اختبار #2
وسيط
prices = [7, 2, 5, 9, 1, 4]
الإخراج المتوقع
7