Sliding Window Maximum
لديك مصفوفة من الأعداد الصحيحة nums وحجم نافذة k. تغطي النافذة k قيم متتالية. تبدأ عند الطرف الأيسر للمصفوفة وتتحرك موضعًا واحدًا إلى اليمين في كل مرة، حتى تقع حافتها اليمنى على القيمة الأخيرة.
أعِد مصفوفة تحتوي على أكبر قيمة داخل النافذة عند كل موضع من مواضعها، من اليسار إلى اليمين. تحتوي المصفوفة ذات الطول n على n-k+1 نافذة، لذا تحتوي النتيجة على n-k+1 قيمة.
الدالة
- numsinteger-array
- المصفوفة التي تنزلق النافذة فوقها
- kinteger
- عدد القيم في كل نافذة
- تُرجعinteger-array
- أكبر قيمة في كل نافذة، من النافذة الموجودة في أقصى اليسار إلى النافذة الموجودة في أقصى اليمين
القيود
1 ≤ k ≤ nums.length ≤ 2 × 104-104 ≤ nums[i] ≤ 104- تحتوي النتيجة على
nums.length-k+1قيمة، واحدة لكل نافذة، بالترتيب من اليسار إلى اليمين.
أمثلة
- المدخلات
- nums = [4, 2, 12, 3, 8, 5, 1]k = 3
- المخرجات
- [12, 12, 12, 8, 8]
- الشرح
- يقع 12 ضمن النوافذ الثلاث الأولى،
[4, 2, 12]و[2, 12, 3]و[12, 3, 8]. بعد خروجه، تحتوي النافذتان[3, 8, 5]و[8, 5, 1]كلتاهما على 8 بوصفه أكبر قيمة.
- المدخلات
- nums = [-3, -1, -7, -2]k = 2
- المخرجات
- [-1, -1, -2]
- الشرح
- النوافذ هي
[-3, -1]و[-1, -7]و[-7, -2]. الأكبر من بين عددين سالبين هو الأقرب إلى الصفر، وهذا يعطينا -1 و-1 و-2.
- المدخلات
- nums = [6, 6, 1]k = 3
- المخرجات
- [6]
- الشرح
- عندما تساوي
kطول المصفوفة، توجد نافذة واحدة هي المصفوفة بأكملها. أكبر قيمة فيها هي 6، ولا تضيف النسخة الثانية من 6 إجابة ثانية.
+15 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك إنشاء طابور يدعم إضافة قيمة إلى الخلف، وإزالة القيمة من الأمام، وقراءة قيمته العظمى الحالية، كلٌّ منها بزمن مُستهلك O(1)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
يتطلب فحص كل نافذة للعثور على أكبر قيمة فيها
kخطوات لكل نافذة. قارن بين نافذتين متجاورتين: فهما تشتركان فيk-1قيمة، لأن قيمة واحدة تخرج من اليسار وأخرى تدخل من اليمين.عندما تدخل قيمة جديدة، لا يمكن لأي قيمة أقدم في النافذة تكون أصغر منها أو مساوية لها أن تكون العظمى مرة أخرى. تظل القيمة الجديدة موجودة في كل نافذة لاحقة ما زالت تحتوي على القيمة الأقدم، وهي أكبر منها أو مساوية لها. يمكنك التخلص من تلك القيم الأقدم نهائيًا.
احتفظ بفهرسة القيم التي تبقى في طابور مزدوج النهاية، بحيث تكون قيمها متناقصة بصرامة من المقدمة إلى المؤخرة. مع كل فهرس جديد، أزل القيم الأصغر أو المساوية من المؤخرة، وأضف الفهرس، وأزل المقدمة إذا خرجت من النافذة، واقرأ القيمة العظمى للنافذة من المقدمة.
الحل
تتشارك النوافذ المتجاورة k-1 قيمة، لذا فإن حساب كل قيمة عظمى من البداية يكرر معظم العمل. تكمن الصعوبة في أن التراجع عن القيمة العظمى غير ممكن: عندما تنزلق أكبر قيمة إلى الخارج من اليسار، تحتاج إلى القيمة الأكبر التالية دون إعادة قراءة النافذة. يحافظ الطابور مزدوج النهاية الرتيب على القيم التي لا يزال من الممكن أن تصبح قيمة عظمى فقط، وبترتيبها، لذا تكون الإجابة دائمًا في مقدمته، ويدخل كل فهرس إليه ويخرج منه مرة واحدة.
افحص كل نافذة
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
تأتي الفكرة الأكثر مباشرة بعد العبارة. النافذة التي تبدأ عند الفهرس start تغطي القيم من start إلى start+k-1. اقرأ تلك القيم وعددها k، واحتفظ بأكبرها، ثم حرّك نقطة البداية خطوة واحدة إلى اليمين. هناك n-k+1 نقطة بداية، من 0 إلى n-k.
هذه الطريقة صحيحة بحكم التعريف: تُقرأ كل نافذة بالكامل، لذا لا يمكن أن تفوت أكبر قيمة فيها. الذاكرة الإضافية هي متغير واحد للاحتفاظ بأكبر قيمة حتى الآن، إضافةً إلى النتيجة.
لكنها بطيئة. تتطلب كل نافذة من النوافذ n-k+1 قراءةً لعدد k من القيم، ويكون حاصل الضرب أكبر ما يمكن عندما تكون k نحو نصف n. عند n = 2 × 10^4 وk = 10^4، يعني ذلك 10^4 نافذة، في كل منها 10^4 قيمة، أي 10^8 قراءة. والأسوأ أن كل نافذتين متجاورتين تشتركان في k-1 قيمة، لذا فإن كل قراءة تقريبًا تكرر قراءةً أجريتها من قبل.
الخوارزمية
- أنشئ قائمة نتائج فارغة.
- كرّر
startمن 0 إلىn-k. - عيّن
bestإلىnums[start]، ثم قارنه بكل قيمة حتىnums[start+k-1]واحتفظ بالقيمة الأكبر. - أضف
bestإلى قائمة النتائج. - أعِد قائمة النتائج.
def maxSlidingWindow(nums, k):
result = []
for start in range(len(nums) - k + 1):
# Read all k values of this window again
result.append(max(nums[i] for i in range(start, start + k)))
return resultالكتل ذات القيم القصوى من كل جانب
الفكرة
قسّم المصفوفة إلى كتل طولها k: الفهارس من 0 إلى k-1، ثم من k إلى 2k-1، وهكذا، مع كتلة أخيرة أقصر إذا لم يكن n من مضاعفات k. طول النافذة هو k بالضبط، لذا إما أن تطابق كتلة واحدة أو تغطي نهاية كتلة وبداية الكتلة التالية. ولا تلامس ثلاث كتل أبدًا.
وهذا يشير إلى استخدام مصفوفتين. تحتوي fromStart[i] على أكبر قيمة من بداية الكتلة التي ينتمي إليها i وحتى i، وتُملأ من اليسار إلى اليمين، مع إعادة ضبطها عند بداية كل كتلة. وتحتوي toEnd[i] على أكبر قيمة من i وحتى نهاية كتلته، وتُملأ من اليمين إلى اليسار، مع إعادة ضبطها عند نهاية كل كتلة. تنتهي النافذة التي تبدأ عند i عند i+k-1. يغطي toEnd[i] الجزء الأيسر منها، ويغطي fromStart[i+k-1] الجزء الأيمن، لذا فإن أكبر قيمة فيها هي الأكبر من القيمتين. عندما تكون النافذة كتلة كاملة، يكون كلا الجزأين مساويًا لأكبر قيمة في تلك الكتلة، وتظل الإجابة صحيحة.
عندما تكون nums = [4, 2, 12, 3, 8, 5, 1] وk = 3، تكون الكتل [4, 2, 12] و[3, 8, 5] و[1]. تكون fromStart هي [4, 4, 12, 3, 8, 8, 1]، وتكون toEnd هي [12, 12, 12, 8, 8, 5, 1]. تبدأ النافذة [2, 12, 3] عند الفهرس 1: تغطي toEnd[1] = 12 القيمتين 2 و12، وتغطي fromStart[3] = 3 القيمة 3، والإجابة هي 12.
تستغرق هذه العملية زمنًا قدره O(n)، عبر ثلاث عمليات مرور على المصفوفة. وتكلفتها استخدام مصفوفتين مساعدتين طول كل منهما n، كما أنها تحتاج إلى المصفوفة كاملة قبل أن تتمكن من الإجابة عن النافذة الأولى.
الخوارزمية
- املأ
fromStartمن اليسار إلى اليمين: انسخnums[i]عندما يكونiمن مضاعفاتk، وإلا فخذ الأكبر منfromStart[i-1]وnums[i]. - املأ
toEndمن اليمين إلى اليسار: انسخnums[i]عندما يكونiهو الفهرس الأخير أو يكونi+1من مضاعفاتk، وإلا فخذ الأكبر منtoEnd[i+1]وnums[i]. - لكل قيمة بداية
iمن 0 إلىn-k، أضف الأكبر منtoEnd[i]وfromStart[i+k-1]. - أعِد النتيجة.
def maxSlidingWindow(nums, k):
n = len(nums)
# Cut nums into blocks of k: indices 0..k-1, k..2k-1, and so on.
from_start = [0] * n # max from the start of i's block up to i
to_end = [0] * n # max from i up to the end of i's block
for i in range(n):
if i % k == 0:
from_start[i] = nums[i]
else:
from_start[i] = max(from_start[i - 1], nums[i])
for i in range(n - 1, -1, -1):
if i == n - 1 or (i + 1) % k == 0:
to_end[i] = nums[i]
else:
to_end[i] = max(to_end[i + 1], nums[i])
# A window [i, i+k-1] is the tail of one block plus the head of the next.
return [max(to_end[i], from_start[i + k - 1]) for i in range(n - k + 1)]طابور مزدوج رتيب من الفهارس
الفكرة
ابدأ بملاحظة واحدة. لنفترض أن الفهرس j يسبق الفهرس i وأن nums[j] ≤ nums[i]. كل نافذة لاحقة ما زالت تحتوي على j تحتوي أيضًا على i، لأن i يقع إلى يمينه ويخرج منها لاحقًا. في كل تلك النوافذ تكون nums[i] أكبر من القيمة نفسها أو مساوية لها، لذا لا يمكن أن يكون j هو القيمة القصوى مرة أخرى. ما إن يصل i، يصبح j بلا فائدة ويمكنك نسيانه.
احتفظ بطابور مزدوج الطرفين للفهرسات التي لم تنسها. عندما يصل i، أزل الفهرسات من الخلف ما دامت قيمها أقل من أو تساوي nums[i]، ثم أضف i. عندها تكون قيم الفهرسات المتبقية متناقصة تناقصًا صارمًا من الأمام إلى الخلف، لأن أي قيمة أقدم لم تكن أكبر كانت ستُزال. لذا يحمل المقدّم أكبر قيمة في النافذة. يخزّن الطابور المزدوج الفهرسات، لا القيم، لأن العنصر الموجود في المقدّم يجب أن يخرج أيضًا عند تجاوز النافذة له: تبدأ النافذة التي تنتهي عند i عند i-k+1، لذا يكون الفهرس i-k هو الذي خرج من النافذة، وإذا كان في المقدّم فأزِله.
تابع nums = [4, 2, 12, 3, 8, 5, 1] مع k = 3، وسجّل القيم في الطابور المزدوج. يدخل 4: [4]. العدد 2 أصغر، لذا ينتظر خلفه: [4, 2]. يزيل 12 العددين كليهما: [12]، وتكون إجابة النافذة الأولى 12. ينتظر 3: [12, 3]، والإجابة 12. يزيل 8 العدد 3: [12, 8]، والإجابة 12. ينتظر 5: [12, 8, 5]، لكن 12 عند الفهرس 2، والنافذة التي تنتهي عند الفهرس 5 تبدأ عند الفهرس 3، لذا يكون 12 قد خرج من النافذة: [8, 5]، والإجابة 8. ينتظر 1: [8, 5, 1]، والإجابة 8.
لماذا التعقيد هو O(n): قد تزيل الحلقة الداخلية عدة فهرسات في خطوة واحدة، لكن كل فهرس يُضاف مرة واحدة ويُزال مرة واحدة على الأكثر، من الخلف عندما تتغلب عليه قيمة أكبر، أو من الأمام عندما يخرج من النافذة. مجموع عمليات الإزالة في التنفيذ كله لا يتجاوز n، لذا لا يتجاوز إجمالي العمل 2n عملية على الطابور المزدوج. يقع كل فهرس في الطابور المزدوج ضمن النافذة الحالية، لذا لا يحتوي أبدًا على أكثر من k فهرسًا.
الخوارزمية
- أنشئ طابورًا مزدوجًا فارغًا للفهرسة وقائمة نتائج فارغة.
- لكل فهرس
i، أزل الفهارس من نهاية الطابور المزدوج ما دام غير فارغ وكانت القيمة عند نهايته أقل من أو تساويnums[i]. - أضف
iإلى النهاية. - إذا كان الفهرس في المقدمة يساوي
i-k، فقد خرج من النافذة: أزله من المقدمة. - بمجرد أن يصبح
i ≥ k-1، تنتهي نافذة كاملة عندi: أضف القيمة عند فهرس المقدمة إلى النتيجة. - أعد النتيجة.
from collections import deque
def maxSlidingWindow(nums, k):
window = deque() # indices; their values strictly decrease from front to back
result = []
for i, x in enumerate(nums):
# A value at the back that is not bigger than x can never be a maximum again.
while window and nums[window[-1]] <= x:
window.pop()
window.append(i)
# The front index has slid out of the window on the left.
if window[0] == i - k:
window.popleft()
# From index k-1 on, every step completes a window; its maximum sits at the front.
if i >= k - 1:
result.append(nums[window[0]])
return result
أخطاء شائعة وحالات حدّية
تأتي معظم الأخطاء من حدود النافذة أو مما يخزّنه الطابور مزدوج النهاية.
- تخزين القيم بدلًا من الفهارس. عندها تحذف العنصر من المقدمة عندما يساوي
nums[i-k]، وهذا يؤدي إلى مشكلة عند وجود قيم مكررة. مع[3, 1, 3]وk = 2، يحذف الرقم 3 الثاني الرقم الأول من الطابور، ثم يُحذف هو نفسه لأنه يساوي القيمة التي خرجت. خزّن الفهارس وقارن مقدمة الطابور معi-k. - إعطاء الإجابة مبكرًا جدًا أو متأخرًا جدًا. تنتهي أول نافذة مكتملة عند الفهرس
k-1، وليس عندk، ويجب أن تحتوي النتيجة علىn-k+1قيمة بالضبط. - حذف الفهرس الخطأ. تبدأ النافذة التي تنتهي عند
iعندi-k+1، لذا فإنi-kهو الفهرس الذي يخرج. حذفi-k+1يزيل قيمة ما تزال ضمن النافذة. - قراءة آخر الطابور أو مقدمته وهو فارغ. تحقّق من أنه يحتوي على عنصر قبل مقارنته بآخره.
- التعامل مع الطابور كما لو كان نسخة من النافذة. فهو لا يحتوي إلا على العناصر المرشحة، وعدد فهارسه يتراوح بين 1 و
k، لذا لا يخبرك حجمه بأي شيء عن النافذة. - في أسلوب الكتل، نسيان أن الكتلة الأخيرة قد تكون أقصر من
k. يجب أن تبدأ عملية المرور من اليمين إلى اليسار من الفهرس الأخير أيضًا، وكذلك من نهاية كل كتلة.
أسئلة شائعة4
ما هو التعقيد الزمني لمسألة إيجاد القيمة العظمى في النافذة المنزلقة؟
يعمل حلّ الطابور مزدوج النهاية الرتيب في زمن O(n). يُضاف كل فهرس مرة واحدة ويُزال مرة واحدة على الأكثر، لذا تنفّذ الحلقة الداخلية ما لا يزيد على n عمليات إزالة خلال التنفيذ كله، حتى لو أزالت عدة عناصر في خطوة واحدة. يحتوي الطابور مزدوج النهاية على k فهارس على الأكثر، لذا تبلغ المساحة الإضافية O(k) فوق مساحة النتيجة.
هل يمكن حل مسألة إيجاد أكبر قيمة في النافذة المنزلقة باستخدام كومة؟
نعم. أضف أزواج القيمة والفهرس إلى كومة عظمى. قبل قراءة العنصر في القمة، أزل العناصر منها ما دامت فهارسها خارج النافذة، إذ لا تُزال العناصر القديمة إلا عند وصولها إلى القمة. يستغرق ذلك وقتًا قدره O(n log n) وقد يحتوي على ما يصل إلى n عنصرًا. أما الطابور مزدوج النهاية فأسرع وأصغر، لأنه يزيل القيم غير المفيدة بمجرد وصول قيمة أكبر.
لماذا يخزّن الطابور مزدوج النهاية الفهارس بدلًا من القيم؟
يجب أن يخرج العنصر الموجود في المقدمة عندما تتجاوزه النافذة، وفهرسه وحده هو ما يخبرك بذلك. باستخدام القيم وحدها، ستضطر إلى التخمين من nums[i-k]، وهذا لا ينجح عندما تظهر القيمة نفسها أكثر من مرة. ويمنحك الفهرس أيضًا القيمة دون أي تكلفة، باستخدام nums[index].
ما الفرق بين الطابور مزدوج النهاية الرتيب والمكدس الرتيب؟
يعمل الجزء الخلفي من الطابور مزدوج النهاية مثل مكدّس رتيب: قبل أن تضيف قيمة، أزل القيم التي تجعلها غير مفيدة. يضيف الطابور مخرجًا ثانيًا من الأمام للقيم التي انتهت صلاحيتها. لا تحتاج مسألة بلا انتهاء صلاحية، مثل إيجاد العنصر الأكبر التالي، إلا إلى المكدّس؛ أما النافذة المنزلقة فتحتاج إلى الطرفين. اعكس المقارنة، وستعطيك الشيفرة نفسها الحد الأدنى لكل نافذة.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def maxSlidingWindow(nums, k):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
nums = [4, 2, 12, 3, 8, 5, 1] k = 3
المتوقع
[12, 12, 12, 8, 8]