Largest Rectangle in Histogram

Q: ما هو التعقيد الزمني لمسألة أكبر مستطيل في المدرج التكراري؟

يعمل حل المكدس الرتيب في زمن O(n) ويستخدم مساحة إضافية O(n) . يُدفع كل فهرس مرة واحدة ويُزال مرة واحدة، وتتطلب كل عملية إزالة مقدارًا ثابتًا من العمل. تجربة كل سلسلة من الأعمدة تستغرق زمنًا O(n²) ، أي نحو 2 × 10^8 خطوة لـ 2 × 10^4 عمود.

صعبالمكدس الرتيب

+10

المدرّج التكراري عبارة عن صف من الأعمدة المتجاورة دون فجوات، عرض كلٍّ منها وحدة واحدة: heights[i] هو ارتفاع العمود i. يغطي المستطيل داخله مجموعة متتابعة من الأعمدة المتجاورة، ولا يمكن أن يزيد ارتفاعه على ارتفاع أقصر عمود في تلك المجموعة.

أعِد أكبر مساحة يمكن أن يكون عليها مثل هذا المستطيل.

الدالة

largestRectangleArea(heights: integer-array) → integer

heightsinteger-array: ارتفاع كل عمود، من اليسار إلى اليمين
تُرجعinteger: مساحة أكبر مستطيل يتسع داخل المدرج التكراري

القيود

1 ≤ heights.length ≤ 2 × 10⁴
0 ≤ heights[i] ≤ 10⁵
عرض كل عمود وحدة واحدة، لذا فإن المستطيل الممتد فوق الأعمدة من i إلى j عرضه j-i+1 وحدة.

أمثلة

المدخلات: heights = [2, 5, 6, 3, 4, 1]
المخرجات: 12
الشرح: ارتفاع الأعمدة الأربعة 5 و6 و3 و4 لا يقل عن 3، لذا يمتد مستطيل بارتفاع 3 فوقها: 3 × 4 = 12. أما أطول عمودين، 5 و6، فيعطيان 5 × 2 = 10 فقط.

+17 اختبارات مخفية عند الإرسال

سؤال إضافي

افترض أن لكل قضيب عرضه الخاص، المحدد في مصفوفة ثانية. ما الذي يتغير في حل المكدس ذي المرور الواحد؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

يمكن أن يبدأ المستطيل وينتهي عند أي عمود، ويعتمد ارتفاعه على أقصر عمود يغطيه، لذا فإن تجربة كل مجموعة متجاورة من الأعمدة تكلّف نحو n²/2 خطوة. والحل هو إعادة صياغة السؤال: أفضل مستطيل يكون ارتفاعه مساويًا تمامًا لارتفاع أحد أعمدته، لذا يحتاج كل عمود فقط إلى معرفة مدى امتداده قبل أن يوقفه عمود أقصر. يعثر المكدس الرتيب على نقاط التوقف هذه لكل عمود، أولًا في مرورين ثم في مرور واحد.

جرّب كل تشغيل مع حدٍّ أدنى متغيّر

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

يغطي المستطيل مجموعة متجاورة من الأعمدة من start إلى end، ويُحدَّد ارتفاعه بأقصر عمود في المجموعة. لذا جرّب كل مجموعة. ثبّت start، ثم زِد end عمودًا في كل مرة، واحتفظ بأقل ارتفاع وصلْت إليه حتى الآن. مساحة أفضل مستطيل في هذه المجموعة هي lowest × (end-start+1).

في [2, 5, 6, 3, 4, 1]، ابدأ من العمود ذي الارتفاع 5. تعطي المجموعات 5 × 1 = 5، ثم 5 × 2 = 10 مع العمود ذي الارتفاع 6، ثم 3 × 3 = 9 عند انضمام العمود ذي الارتفاع 3، و3 × 4 = 12 مع العمود ذي الارتفاع 4، و1 × 5 = 5 مع العمود ذي الارتفاع 1. والإجابة هي 12. إن تحديث lowest مع نمو المجموعة يجعل كل خطوة O(1)، لذلك لن تعيد مسح أي مجموعة للعثور على أقصر أعمدتها.

هذه الطريقة صحيحة لأن كل مستطيل يقع فوق مجموعة ما، وبالنسبة إلى مجموعة ثابتة، فإن أطول مستطيل يمكن أن يلائمها يساوي ارتفاعه ارتفاع أقصر عمود فيها تمامًا. لكنها بطيئة لأن عدد المجموعات هو n(n+1)/2: نحو 2 × 10^8 لمجموعة تضم 2 × 10^4 عمود، وهذا العدد لا يعتمد إطلاقًا على الارتفاعات. تتوقف معظم هذه المجموعات بسبب عمود منخفض قبل نهايتها بوقت طويل، ومع ذلك تواصل طريقة القوة الغاشمة تمديدها.

الخوارزمية

عيّن best إلى 0.
لكل start، عيّن lowest إلى heights[start].
لكل end من start إلى آخر عمود، خفّض lowest إلى heights[end] إذا كان ذلك العمود أقصر.
حدّث best باستخدام lowest × (end-start+1).
أعِد best.

def largestRectangleArea(heights):
    n = len(heights)
    best = 0
    for start in range(n):
        lowest = heights[start]
        for end in range(start, n):
            # The rectangle over start..end is as tall as the lowest bar in it.
            lowest = min(lowest, heights[end])
            best = max(best, lowest * (end - start + 1))
    return best

أقرب عمود أقصر على كل جانب

الفكرة

اعكس اتجاه البحث. في أفضل مستطيل، يوجد تحته شريط واحد على الأقل ارتفاعه مطابق تمامًا لارتفاع المستطيل؛ وإلا لأمكنك رفع المستطيل. لذا فالإجابة هي أكبر قيمة، عبر جميع الأشرطة i، لمستطيل ارتفاعه heights[i] تمامًا ويمتد لأكبر عرض ممكن. يمتد حتى يصادف شريطًا أقصر منه تمامًا على كل جانب. سمِّ فهرسيهما left[i] وright[i]، واستخدم -1 وn عند عدم وجود شريط كهذا. يغطي المستطيل الأشرطة الواقعة بينهما فقط: العرض right[i]-left[i]-1. وهكذا نحصل على n احتمالات بدلًا من n²/2.

لإيجاد left[i] لكل شريط، تحرّك من اليسار إلى اليمين مستخدمًا مكدسًا من الفهارس التي تزداد ارتفاعاتها بصرامة من الأسفل إلى الأعلى. عند وصول الشريط i، أزل من المكدس كل فهرس يكون شريطه بارتفاع heights[i] أو أعلى. لا يمكن لهذه الأشرطة أن تكون أقرب شريط أقصر إلى i أو إلى أي شريط يأتي بعده، لأن i أقرب وليس أعلى منها. ما يبقى في القمة هو أقرب شريط أقصر إلى اليسار. ثم أضف i إلى المكدس. وتُعطي العملية نفسها من اليمين إلى اليسار right[i].

بالنسبة إلى [2, 5, 6, 3, 4, 1]، تعطي العمليتان left = [-1, 0, 1, 0, 3, -1] وright = [5, 3, 3, 5, 5, 6]. يتوقف الشريط الذي ارتفاعه 3 عند الفهرس 3 بسبب الشريط الذي ارتفاعه 2 عند الفهرس 0 والشريط الذي ارتفاعه 1 عند الفهرس 5، لذا يكون مستطيله 3 × (5-0-1) = 12. أما الشريط الذي ارتفاعه 6 فتحاصره الأشرطة المجاورة، ولا يعطي إلا 6 × 1.

يُضاف كل فهرس إلى المكدس مرة واحدة ويُزال منه مرة واحدة على الأكثر في كل عملية، لذا فكلتا العمليتين تستغرقان O(n)، حتى لو أزال شريط واحد أشرطة كثيرة من المكدس. والتكلفة هي مصفوفتان إضافيتان.

الخوارزمية

تحرّك من اليسار إلى اليمين مع مكدّس فارغ. لكل i، أزل العناصر من المكدّس ما دام الشريط في أعلاه بارتفاع heights[i] أو أكثر؛ عيّن left[i] إلى العنصر في الأعلى، أو إلى -1 إذا كان المكدّس فارغًا؛ ثم أضف i إلى المكدّس.
تحرّك من اليمين إلى اليسار بالطريقة نفسها لملء right[i]، مستخدمًا n عندما يكون المكدّس فارغًا.
لكل i، احسب heights[i] × (right[i]-left[i]-1).
أعِد أكبر قيمة من هذه المساحات.

def largestRectangleArea(heights):
    n = len(heights)
    left = [-1] * n  # index of the nearest shorter bar on the left, or -1
    right = [n] * n  # index of the nearest shorter bar on the right, or n
    stack = []  # indices whose heights rise strictly from bottom to top
    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        if stack:
            left[i] = stack[-1]
        stack.append(i)
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        if stack:
            right[i] = stack[-1]
        stack.append(i)
    best = 0
    for i in range(n):
        # Bar i is the lowest bar of everything strictly between left[i] and right[i].
        best = max(best, heights[i] * (right[i] - left[i] - 1))
    return best

مرور واحد باستخدام مكدس رتيب

الفكرة

تمريرة اليسار إلى اليمين ترى بالفعل كل الحدود اليمنى؛ لكنها تتجاهلها. عندما يزيل العمود i العمود t من المكدس، فإن heights[i] ليس أطول من heights[t]، لذا فإن i هو الموضع الذي يتوقف عنده مستطيل t من اليمين. والمؤشر الموجود مباشرةً أسفل t في المكدس هو الموضع الذي يتوقف عنده من اليسار. لذا قِس المستطيل لحظة الإزالة من المكدس: heights[t] × (i - below - 1)، حيث إن below هو العنصر الجديد في أعلى المكدس، أو -1 إذا أصبح المكدس فارغًا.

الثابت: تزداد الارتفاعات في المكدس بصرامة من الأسفل إلى الأعلى، والمؤشر أسفل كل عنصر هو أقرب عمود إلى يساره يكون أقصر منه. أُزيل كل عمود بينهما من المكدس أثناء المعالجة، إما بواسطة العنصر نفسه أو بواسطة عمود أزاله العنصر لاحقًا، لذا لا يقل ارتفاع أي منها عن ارتفاع العنصر. تصل الأعمدة التي لا تُزال أبدًا إلى النهاية، لذا بعد معالجة العمود الأخير، عالِج عمودًا إضافيًا ارتفاعه 0. فهو أقصر من كل شيء ويفرغ المكدس.

تتبّع [2, 5, 6, 3, 4, 1]. أضف 2 و5 و6: يحتوي المكدس على المؤشرات [0, 1, 2]. يزيل العدد 3 عند المؤشر 3 العمود 6 (المساحة 6 × (3-1-1) = 6) والعمود 5 (المساحة 5 × (3-0-1) = 10)، ثم يتوقف عند العمود 2 ويُضاف إلى المكدس. أضف 4. يزيل العدد 1 عند المؤشر 5 العمود 4 (المساحة 4)، ثم العمود 3، ويمتد مستطيله من المؤشر 1 إلى 4: 3 × (5-0-1) = 12. ويزيل العمود 2 أيضًا (2 × 5 = 10، والمكدس فارغ، لذا العرض هو 5). يزيل الصفر الختامي العمود 1 (1 × 6 = 6). أفضل مساحة هي 12.

تعني الإزالة عند >= أن عمودًا مساويًا قد يجعل عمودًا آخر يتوقف مبكرًا. وهذا آمن: فالعمود المساوي يحل محله في المكدس، ويرث الحد الأيسر نفسه، وعندما يُزال لاحقًا يغطي مستطيله الامتداد كله. في [3, 3, 3, 3] تسجل الأعمدة الثلاثة الأولى ذات الارتفاع 3 عروضًا مقدارها 1 و2 و3، ويزيل الصفر الختامي العمود الأخير بعرض 4، فتكون المساحة 12.

الخوارزمية

ابدأ بمكدس فارغ من الفهارس وbest = 0.
من أجل i من 0 إلى n، اجعل الارتفاع الحالي هو heights[i]، أو 0 عندما i = n.
ما دام العمود الموجود أعلى المكدس لا يقل ارتفاعًا عن الارتفاع الحالي، أزِله باعتباره t؛ العرض هو i - below - 1، حيث below هو العنصر الجديد في الأعلى أو -1؛ حدّث best باستخدام heights[t] × width.
أضف i إلى المكدس.
أعِد best.

def largestRectangleArea(heights):
    n = len(heights)
    stack = []  # indices whose heights rise strictly from bottom to top
    best = 0
    for i in range(n + 1):
        current = heights[i] if i < n else 0  # a bar of 0 past the end empties the stack
        while stack and heights[stack[-1]] >= current:
            # Bar i stops the popped bar on the right; the bar below it stops it on the left.
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            best = max(best, height * (i - left - 1))
        stack.append(i)
    return best

أخطاء شائعة وحالات حدّية

حلقة المكدس قصيرة، وتقع جميع الأخطاء تقريبًا في حساب العرض أو في الأعمدة المتبقية في النهاية.

نسيان الأعمدة التي لا تزال في المكدس. في مدرج تكراري متزايد مثل [1, 2, 3, 4, 5]، لا يُزال أي عنصر من المكدس داخل الحلقة، ومن دون العمود الختامي ذي الارتفاع 0، تُرجع 0 بدلًا من 9.
قياس العرض انطلاقًا من فهرس العمود المُزال من المكدس نفسه. يبدأ مستطيله مباشرةً بعد العمود الذي تحته في المكدس، وليس عنده: في [2, 5, 6, 3, 4, 1]، يمتد العمود ذو الارتفاع 3 عند الفهرس 3 من الفهرس 1 إلى 4. استخدام i - t يعطي 2 بدلًا من 4.
استخدام عرض خاطئ عندما يصبح المكدس فارغًا بعد إزالة عنصر منه. فالعمود المُزال هو الأدنى حتى الآن، لذا يمتد مستطيله حتى الفهرس 0 ويكون العرض i. في [2, 1, 2]، يمتد العمود ذو الارتفاع 1 على الأعمدة الثلاثة كلها، ومساحته 3.
التوقف عند الأعمدة المتساوية على كلا الجانبين في نسخة المرورين. عندئذٍ، في [3, 3, 3, 3]، يرى كل عمود عرضًا مقداره 1، وتُرجع 3 بدلًا من 12. أزل العناصر عند استخدام >=، لتكون الحدود أعمدة أقصر منه تمامًا.
افتراض أن العمود الأعلى أو الامتداد الأعرض هو الذي يعطي الإجابة. في [2, 5, 6, 3, 4, 1]، لا يعطي العمود ذو الارتفاع 6 ولا العرض الكامل البالغ 6 أعمدة الإجابة؛ بل يعطيها ارتفاع متوسط على عرض متوسط.
تجاوز السعة. تصل المساحة هنا إلى 10^5 × 2 × 10^4 = 2 × 10^9، وهذا لا يزال ضمن نطاق عدد صحيح موقّع من 32 بت؛ أما مع الحدود الأكبر، فأجرِ الضرب باستخدام 64 بت.

أسئلة شائعة4

ما هو التعقيد الزمني لمسألة أكبر مستطيل في المدرج التكراري؟

يعمل حل المكدس الرتيب في زمن O(n) ويستخدم مساحة إضافية O(n). يُدفع كل فهرس مرة واحدة ويُزال مرة واحدة، وتتطلب كل عملية إزالة مقدارًا ثابتًا من العمل. تجربة كل سلسلة من الأعمدة تستغرق زمنًا O(n²)، أي نحو 2 × 10^8 خطوة لـ 2 × 10^4 عمود.

لماذا يُقاس مستطيل الشريط عند إظهاره؟

يُزال الشريط بواسطة أول شريط على يمينه لا يزيد ارتفاعه عنه، لذا ينتهي مستطيله عنده من جهة اليمين. الفهرس الموجود تحته في المكدس هو أقرب شريط أقصر منه إلى يساره، لذا ينتهي عنده من جهة اليسار. عند لحظة الإزالة يكون الطرفان معروفين، وتكون المساحة height × (i - below - 1).

هل يمكن حل مسألة أكبر مستطيل في المدرج التكراري باستخدام أسلوب تقسيم المشكلة وحلها؟

نعم. إما أن يقع أدنى عمود في النطاق بأكمله أسفل أفضل مستطيل، فتكون مساحته عندئذٍ lowest × width، أو يقسم النطاق إلى جزء أيسر وآخر أيمن تحلّهما كلًّا على حدة. باستخدام مسح خطي لإيجاد الحد الأدنى، تكون التعقيدية O(n log n) على مدخلات عشوائية، لكنها O(n²) على مدخلات مرتبة؛ أما شجرة المقاطع لإيجاد الحدود الدنيا للنطاقات فتجعلها O(n log n) دائمًا. المكدس أبسط وأسرع.

كيف تُستخدم مسألة أكبر مستطيل في المدرج التكراري لإيجاد المستطيل الأكبر في شبكة من الأصفار والآحاد؟

امسح الشبكة صفًا تلو الآخر، واحتفظ لكل عمود بعدد قيم 1 المتتالية المنتهية عند الصف الحالي؛ وتُعيد القيمة 0 هذا العدد إلى الصفر. تشكّل أعداد كل صف مخططًا بيانيًا بالأعمدة، وأكبر مستطيل من القيم 1 ينتهي عند ذلك الصف هو أكبر مستطيل في ذلك المخطط. يؤدي تشغيل المكدس مرة واحدة لكل صف إلى حل الشبكة في زمن O(rows × cols).

Python

def largestRectangleArea(heights):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

heights = [2, 5, 6, 3, 4, 1]

المتوقع

Largest Rectangle in Histogram

الدالة

القيود

أمثلة

تلميحات

الحل

جرّب كل تشغيل مع حدٍّ أدنى متغيّر

أقرب عمود أقصر على كل جانب

مرور واحد باستخدام مكدس رتيب

أخطاء شائعة وحالات حدّية

أسئلة شائعة4

مسائل مشابهة