Stock Span Problem
تحصل على سعر الإغلاق لسهم في كل يوم: prices[i] هو السعر في اليوم i. امتداد اليوم i هو عدد الأيام المتتالية، المنتهية باليوم i مع احتسابه، التي كان فيها السعر أقل من أو يساوي prices[i].
أعِد امتداد كل يوم، بالترتيب نفسه الوارد في prices. كل امتداد لا يقل عن 1، لأن اليوم يُحتسب دائمًا ضمن امتداده.
الدالة
- pricesinteger-array
- السعر في كل يوم، بالترتيب
- تُرجعinteger-array
- مدة كل يوم، بالترتيب نفسه
القيود
1 ≤ prices.length ≤ 1041 ≤ prices[i] ≤ 105- يُحتسب اليوم الأسبق ذو السعر نفسه ضمن المدة؛ ولا يوقفها إلا سعر أعلى منه تمامًا.
أمثلة
- المدخلات
- prices = [31, 27, 14, 21, 30, 18, 40]
- المخرجات
- [1, 1, 1, 2, 4, 1, 7]
- الشرح
- اليوم 3 عند 21 يعود إلى ما قبل 14 ويتوقف عند 27: النطاق 2. اليوم 4 عند 30 يتوقف عند 31: النطاق 4. اليوم 6 عند 40 يتجاوز كل الأسعار السابقة ويغطي الأيام السبعة كلها.
- المدخلات
- prices = [8, 8, 3, 8]
- المخرجات
- [1, 2, 1, 4]
- الشرح
- تُحتسب الأسعار المتساوية، لذا يغطي اليوم 1 بسعر 8 اليوم 0، ويحصل على 2. ويغطي اليوم 3 بسعر 8 اليوم 3 وكلا السعرين السابقين 8، أي نطاقًا من 4.
- المدخلات
- prices = [50, 40, 30, 20]
- المخرجات
- [1, 1, 1, 1]
- الشرح
- كل يوم أقل تكلفة من اليوم الذي سبقه، لذا لا يمتد أي نطاق إلى ما قبل اليوم نفسه، ويكون كل نطاق بقيمة 1.
سؤال إضافي
تصل الأسعار الآن واحدًا تلو الآخر، وعليك الإبلاغ عن كل فترة بمجرد ورود سعرها. ما النهج الذي يظل صالحًا، وما الذي يحتفظ به بين الاستدعاءات؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
العدّ التنازلي من كل يوم يكرر العمل: فعلى مدى 8000 يوم بالسعر نفسه، يعود اليوم الأخير وحده إلى الوراء 8000 يوم. عندما تعود إلى الوراء انطلاقًا من اليوم، ما الأيام السابقة التي يمكنك تخطيها نهائيًا؟
بمجرد أن يصبح سعر اليوم مساويًا على الأقل لسعر يوم سابق، لا يمكن لذلك اليوم السابق أن يكون اليوم الذي يوقف فترة لاحقة: فاليوم أقرب وسعره لا يقل عن سعره. الأيام التي يظل سعرها أعلى من أسعار جميع الأيام التي تليها هي وحدها المهمة، وأسعارها تنخفض من الأقدم إلى الأحدث.
مرّ على الأيام بالترتيب واحتفظ بالأيام السابقة التي لا تزال مهمة في مكدس، على هيئة فهارس. قبل أن تجيب عن اليوم، أزل من المكدس كل يوم كان سعره أقل من سعر اليوم أو مساويًا له. يعني المكدس الفارغ أن المدة تمتد إلى اليوم 0؛ وإلا فتتوقف بعد يوم واحد من اليوم المتبقي في أعلى المكدس. ثم أضف اليوم إلى المكدس.
الحل
ينتهي امتداد اليوم عند أقرب يوم سابق ذي سعر أعلى منه بشكل صارم. يتطلب الرجوع للعثور عليه ما يصل إلى n خطوة لكل يوم. بدلًا من ذلك، احتفظ فقط بالأيام التي لا يزال بإمكانها إيقاف امتداد مستقبلي: يعثر مكدس من الفهارس ذات الأسعار المتناقصة بشكل صارم على كل حد في مرور واحد.
عدّ تنازليًا من كل يوم
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
اتبع التعريف. بالنسبة إلى اليوم i، ارجع يومًا واحدًا في كل مرة ما دام السعر في ذلك اليوم أقل من أو يساوي prices[i]، مع احتساب اليوم i أيضًا. ينتهي الامتداد عند أول سعر أعلى تمامًا أو عند بداية المصفوفة.
لا يعيد أيٌّ من عمليات الاجتياز استخدام عملية سابقة. عندما تكون الأسعار ثابتة أو مرتفعة، يعود كل اجتياز إلى اليوم 0: تعني n = 10^4 أيام نحو 5 × 10^7 خطوة.
الخوارزمية
- أنشئ
span، وهي مصفوفة بطولprices. - لكل يوم
i، عيّن العداد إلى 0 والمؤشرjإلىi. - ما دام
j ≥ 0وprices[j] ≤ prices[i]، أضف 1 إلى العداد وحرّكjيومًا إلى الخلف. - خزّن العداد في
span[i]. بعد اليوم الأخير، أعدspan.
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 spanمكدس تنازلي رتيب للأيام الأعلى
الفكرة
سمِّ اليوم الأسبق الأقرب الذي يكون سعره أعلى تمامًا بالحاجب. المدى هو today - blocker، أو today + 1 عندما لا يوجد يوم كهذا.
في المثال الأول، تكلفة اليوم 3 هي 21 وتكلفة اليوم 4 هي 30. تصل كل جولة لاحقة إلى اليوم 4 أولًا، وأي سعر يتجاوز 30 يتجاوز أيضًا 21، لذا لا يمكن لليوم 3 أن يكون حاجبًا مرة أخرى. عمومًا، عند وصول اليوم الحالي، يكون قد انتهى دور كل مرشح أسبق سعره أقل من أو يساوي سعر اليوم الحالي: أزِله. اليوم المتبقي في أعلى المكدس هو الحاجب لليوم الحالي. ثم أضف اليوم الحالي إلى المكدس.
تنخفض الأسعار في المكدس بصرامة من الأسفل إلى الأعلى، لذا فإن أول سعر يبقى هو أقرب سعر أعلى. في المثال الأول، يزيل اليوم 4 اليومين 3 و1، ويتوقف عند اليوم 0، ويكون المدى 4 - 0 = 4. يُضاف كل يوم إلى المكدس مرة واحدة ويُزال منه مرة واحدة كحد أقصى، لذا تعمل العملية في O(n).
الخوارزمية
- أنشئ مصفوفة
spanومكدسًا فارغًا لفهارس الأيام. - لكل يوم
today، أخرج الفهارس من المكدس ما دام سعرها أقل من أو يساويprices[today]. - إذا كان المكدس فارغًا، فإن قيمة الامتداد هي
today + 1؛ وإلا فهيtodayناقص الفهرس الموجود في الأعلى. - أضف
todayإلى المكدس وانتقل إلى اليوم التالي. أعدspan.
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
أخطاء شائعة وحالات حدّية
- الإزالة عند
<بدلًا من<=. في[8, 8, 3, 8]، المدى لليوم الأخير هو 4؛ أما التوقف عند الرقم 8 السابق فيعطي 2. - كتابة
todayبدلًا منtoday + 1عندما يكون المكدس فارغًا. يجب أن يحصل اليوم 0 على 1، لا 0. - الإزالة مرة واحدة فقط في اليوم. في المثال الأول، يجب أن يتجاوز 40 الأيام 5 و4 و0. إذا توقفت بعد اليوم 5، فسيبدو اليوم 4 كأنه الحاجز، ما يعطي مدى قدره 2 بدلًا من 7.
- في Lua وR، تبدأ المصفوفات من 1. عند استخدام فهارس تبدأ من 1، يكون المدى عند فراغ المكدس هو
today، لاtoday + 1.
أسئلة شائعة4
ما هو التعقيد الزمني لمسألة نطاق أسعار الأسهم؟
زمن O(n) ومساحة إضافية O(n) باستخدام المكدس الرتيب، لأن كل يوم يغادر المكدس مرة واحدة على الأكثر. أما السير إلى الخلف انطلاقًا من كل يوم فيستغرق O(n²) عندما تستمر الأسعار في الارتفاع أو تبقى ثابتة.
هل ينبغي أن يخزّن المكدس الأسعار أم مؤشرات الأيام؟
فهارس الأيام. المدى هو عدد الأيام، ولا يعطيك ذلك إلا فهرس الحاجز. تقرأ prices[index] السعر لاستخدامه في المقارنة.
هل يمكن حل مشكلة نطاق أسعار الأسهم دون استخدام مكدس منفصل؟
نعم. ابدأ عند j = today - 1؛ ما دام j ≥ 0 وprices[j] ≤ prices[today]، فقفز إلى j - span[j]، لأن سعر كل يوم ضمن ذلك الامتداد لا يتجاوز prices[j]. الامتداد هو today - j. لا تقع القفزات إلا على الأيام التي سيحتفظ بها المكدّس، لذا يظل المرور O(n).
هل تُعدّ مشكلة نطاق الأسهم مشكلة العنصر الأكبر السابق؟
نعم، يُقاس ذلك بالأيام: لكل يوم، ابحث عن أقرب يوم سابق كان سعره أعلى بشكل صارم، واذكر كم يومًا يفصلك عنه. اعكس اتجاه المسح أو المقارنة، وستمنحك المكدسة نفسها اليوم التالي ذي السعر الأعلى، أو اليوم التالي ذي السعر الأقل، أو اليوم السابق ذي السعر الأقل.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def stockSpan(prices):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
prices = [31, 27, 14, 21, 30, 18, 40]
الإخراج المتوقع
[1, 1, 1, 2, 4, 1, 7]