Sliding Window Maximum
لديك مصفوفة من الأعداد الصحيحة nums وحجم نافذة k. تبدأ نافذة تضم k قيمة متتالية من الطرف الأيسر وتتحرك نحو اليمين موضعًا واحدًا في كل مرة، حتى تصل حافتها اليمنى إلى القيمة الأخيرة. أعد أكبر قيمة في النافذة عند كل موضع، من اليسار إلى اليمين: n-k+1 قيمة لمصفوفة طولها n.
الدالة
- 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 ضمن النوافذ الثلاث الأولى، لذا تكون الإجابة في كل منها 12. بعد خروجه، يكون 8 هو أكبر قيمة في كل من
[3, 8, 5]و[8, 5, 1].
- المدخلات
- 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 إلى إجابة ثانية.
سؤال إضافي
هل يمكنك إنشاء طابور يدعم إضافة قيمة إلى الخلف، وإزالة القيمة الموجودة في الأمام، وقراءة قيمته القصوى الحالية، وكل ذلك في زمن مستهلك O(1)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
يتطلب فحص كل نافذة للعثور على أكبر قيمة فيها
kخطوات لكل نافذة. قارن نافذتين متجاورتين: تشتركان فيk-1قيمة، لأن قيمة واحدة تغادر من اليسار وتدخل قيمة أخرى من اليمين.عندما تدخل قيمة جديدة، لا يمكن لأي قيمة أقدم في النافذة أصغر منها أو مساوية لها أن تكون القيمة العظمى مجددًا. تبقى القيمة الجديدة في كل نافذة لاحقة لا تزال تحتوي على القيمة الأقدم، وهي على الأقل مساوية لها في الكِبَر. يمكنك التخلص نهائيًا من تلك القيم الأقدم.
احتفظ بفهرسة القيم التي تبقى في طابور مزدوج النهاية، بحيث تتناقص قيمها تناقصًا صارمًا من المقدمة إلى المؤخرة. لكل فهرس جديد، أزل من المؤخرة القيم الأصغر أو المساوية، ثم أضف الفهرس، وأزل العنصر من المقدمة إذا خرج من النافذة، واقرأ القيمة القصوى للنافذة من المقدمة.
الحل
تتشارك النوافذ المتجاورة k-1 قيمة، لذا فإن إعادة حساب كل قيمة عظمى تكرر معظم العمل. لكن لا يمكن التراجع عن القيمة العظمى: فعندما تخرج أكبر قيمة من النافذة، تحتاج إلى القيمة التالية الأكبر من دون قراءة النافذة مجددًا. يحتفظ الطابور مزدوج النهاية الرتيب بالقيم التي لا يزال من الممكن أن تصبح قيمة عظمى، وتكون الإجابة عند مقدمته.
افحص كل نافذة
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
اقرأ قيم k لكل نافذة واحتفظ بالقيمة الأكبر. تُقرأ كل نافذة بالكامل، لذا لا يمكن أن تفوتك قيمتها القصوى. تتطلب كل نافذة من النوافذ البالغ عددها n-k+1 عدد k من عمليات القراءة، ويكون الأسوأ عندما تكون k نحو نصف n: تعطي n = 2 × 10^4 وk = 10^4 نحو 10^4 نافذة، في كل منها 10^4 قيمة، أي 10^8 عملية قراءة.
الخوارزمية
- كرّر
startمن 0 إلىn-k. - خذ أكبر قيمة من
nums[start]حتىnums[start+k-1]. - أضِفها إلى النتيجة، وأعِد النتيجة بعد انتهاء الحلقة.
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، وهكذا، مع كتلة أخيرة أقصر إذا لم يكن k يقسم n. طول النافذة هو k بالضبط، لذا فهي إما كتلة كاملة أو نهاية كتلة مع بداية الكتلة التالية.
لذا احسب مسبقًا fromStart[i]، وهي أكبر قيمة من بداية كتلة i حتى i، وtoEnd[i]، وهي أكبر قيمة من i حتى نهاية كتلته. تنتهي النافذة التي تبدأ عند i عند i+k-1: تغطي toEnd[i] جزأها الأيسر، ويغطي fromStart[i+k-1] جزأها الأيمن، لذا تكون القيمة الأكبر هي أقصاها. في المثال الأول، تأخذ النافذة [2, 12, 3] القيمتين toEnd[1] = 12 وfromStart[3] = 3، فتكون النتيجة 12.
توفر ثلاث تمريرات زمنًا قدره O(n)، مقابل استخدام مصفوفتين مساعدتين طول كل منهما n والحاجة إلى المصفوفة كاملة قبل الحصول على الإجابة الأولى.
الخوارزمية
- املأ
fromStartمن اليسار إلى اليمين، وأعد البدء باستخدامnums[i]عندما يكونiمن مضاعفاتk. - املأ
toEndمن اليمين إلى اليسار، وأعد البدء باستخدامnums[i]عند الفهرس الأخير وكلما كانi+1من مضاعفاتk. - لكل بداية
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 أبدًا قيمة عظمى مرة أخرى: كل نافذة لاحقة تحتوي على j تحتوي أيضًا على i، الذي يغادر بعدها. لذا، عند وصول i، يمكنك نسيان j.
احتفظ بطابور مزدوج للفهرسة التي لم تُنسَ بعد. عند وصول i، أزل الفهارس من النهاية ما دامت قيمها أقل من أو تساوي nums[i]، ثم أضف i. تتناقص القيم المتبقية تناقصًا صارمًا من المقدمة إلى النهاية، لذا تكون قيمة المقدمة هي القيمة العظمى في النافذة. خزّن الفهارس، لأن الفهرس الموجود في المقدمة يجب أن يغادر أيضًا عندما تتجاوزه النافذة. في المثال الأول، عند الفهرس 5، يحتوي الطابور المزدوج على 12 و8 و5؛ تقع 12 عند الفهرس 5 - 3 = 2، لذا تغادر وتكون الإجابة 8.
يُضاف كل فهرس مرة واحدة ويُزال مرة واحدة على الأكثر: بحد أقصى 2n عملية على الطابور المزدوج، بزمن O(n). ولا يحتوي الطابور المزدوج أبدًا على أكثر من k فهارس.
الخوارزمية
- لكل فهرس
i، أخرج الفهارس من نهاية الطابور مزدوج النهاية ما دام غير فارغ وكانت القيمة عند نهايته أقل من أو تساويnums[i]. - أضف
iإلى نهاية الطابور. - إذا كان الفهرس في المقدمة يساوي
i-k، فهذا يعني أنه غادر النافذة: أخرجه. - بمجرد أن يصبح
i ≥ k-1، أضف القيمة عند الفهرس الموجود في المقدمة إلى النتيجة.
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
أخطاء شائعة وحالات حدّية
- تخزين القيم بدلًا من الفهارس. مع
[3, 1, 3]وk = 2، يُخرج الرقم 3 الثاني الرقم 3 الأول من الطابور، ثم يُزال هو نفسه لأنه يساويnums[0]، وهي القيمة التي غادرت. - إعطاء الإجابة مبكرًا جدًا أو متأخرًا جدًا. تنتهي أول نافذة كاملة عند الفهرس
k-1، ويجب أن تحتوي النتيجة علىn-k+1قيمة بالضبط. - إزالة
i-k+1بدلًا منi-k. فهذا الفهرس لا يزال يشير إلى أول قيمة في النافذة. - قراءة العنصر الأخير في الطابور مزدوج النهاية من دون التحقق من أنه يحتوي على عنصر.
- في أسلوب الكتل، نسيان أن الكتلة الأخيرة قد تكون أقصر من
k. يجب أن تبدأ عملية المرور من اليمين إلى اليسار من الفهرس الأخير، وكذلك عند نهاية كل كتلة.
أسئلة شائعة3
ما التعقيد الزمني لمسألة إيجاد القيمة القصوى في النافذة المنزلقة؟
يعمل حلّ الطابور مزدوج النهاية الرتيب في زمن O(n)، لأن كل فهرس يُضاف مرة واحدة ويُزال مرة واحدة على الأكثر. يحتوي الطابور على k فهارس كحد أقصى، لذا فإن المساحة الإضافية هي O(k) بالإضافة إلى مساحة النتيجة.
هل يمكن حل مسألة أكبر قيمة في النافذة المنزلقة باستخدام كومة؟
نعم. أضف أزواجًا من القيمة والفهرس إلى كومة عظمى، وقبل قراءة العنصر الأعلى، أزِله ما دام فهرسه خارج النافذة. يستغرق ذلك زمنًا قدره O(n log n)، ويمكن أن يحتوي على ما يصل إلى n من العناصر. الطابور مزدوج النهاية أسرع وأصغر لأنه يتخلص من القيم غير المفيدة فور وصول قيمة أكبر.
ما الفرق بين الطابور مزدوج النهاية الرتيب والمكدس الرتيب؟
يعمل الطرف الخلفي من طابور مزدوج مثل مكدس رتيب: قبل أن تضيف قيمة، تزيل القيم التي تجعلها بلا فائدة. يضيف الطابور المزدوج مخرجًا من الأمام للقيم القديمة جدًا. لا يحتوي العنصر الأكبر التالي على انتهاء صلاحية، لذا لا يحتاج إلا إلى المكدس. اعكس المقارنة، وسيعطيك الطابور المزدوج الحد الأدنى لكل نافذة.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def maxSlidingWindow(nums, k):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
nums = [4, 2, 12, 3, 8, 5, 1] k = 3
الإخراج المتوقع
[12, 12, 12, 8, 8]