Container With Most Water
لديك قائمة height من الأعداد الصحيحة غير السالبة. يمثّل الخط i جدارًا رأسيًا ارتفاعه height[i] يقف عند الموضع i. يشكّل أي خطّين حاويةً مع الأرض، ويمكنها احتواء كمية من الماء تساوي ارتفاع الخط الأقصر مضروبًا في المسافة بين الخطين. لا تعيق الخطوط الأخرى ذلك. أعد أكبر كمية من الماء يمكن لزوج واحد من الخطوط احتواؤها.
الدالة
- heightinteger-array
- ارتفاعات الخطوط عند المواضع 0 و1 و2 وما إلى ذلك
- تُرجعinteger
- أكبر كمية من الماء يمكن أن يتسع لها سطران
القيود
2 ≤ height.length ≤ 1040 ≤ height[i] ≤ 104- الإجابة لا تتجاوز 108، لذا يمكن تمثيلها بعدد صحيح ذي 32 بتًا.
أمثلة
- المدخلات
- height = [3, 7, 2, 5, 4, 7, 3, 6]
- المخرجات
- 36
- الشرح
- يقع الخطان عند الموضعين 1 و7، وارتفاعاهما 7 و6، على بُعد 6 وحدات ويحتويان على 6 × 6 = 36. أما الخطان الأطول، وهما الخطان بارتفاع 7 عند الموضعين 1 و5، فلا يحتويان إلا على 7 × 4 = 28.
- المدخلات
- height = [4, 4]
- المخرجات
- 4
- الشرح
- يشكّل سطران حاوية واحدة بالضبط: ارتفاعها 4 وعرضها 1، لذا تتسع لـ 4.
سؤال إضافي
هنا يتم تجاهل الخطوط الواقعة بين الخطين لديك. لو كان كل خط عبارة عن حاجز صلب، فكمية الماء التي ستتجمع بينها جميعًا؟ هل يمكنك حساب ذلك أيضًا في O(n)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
ابدأ بالخطين الخارجيين: فهما يشكّلان أوسع حاوية. تحريك أيٍّ من الطرفين إلى الداخل يكلّف وحدة واحدة من العرض. أيّ الخطين يمكنه تعويض ذلك؟
يُحدَّد مستوى الماء بالخط الأقصر. نقل الخط الأطول نحو الداخل يُبقي هذا المستوى ويقلّل العرض، لذا لا يمكن أن يفيد أبدًا. وحده استبدال الخط الأقصر قد يفيد.
أبقِ مؤشرًا عند كل طرف. قِس كمية الماء بينهما واحتفظ بأفضل قيمة، ثم حرّك المؤشر عند الخط الأقصر خطوةً واحدة إلى الداخل. توقّف عندما يلتقي المؤشران.
الحل
فحص جميع الأزواج وعددها n²/2 يعني إجراء 5 × 10^7 عملية ضرب عند وجود 10^4 خطوط. تعتمد كمية الماء فقط على الخط الأقصر في الزوج، لذا بمجرد أن يكون خط ما هو الجانب الأقصر لأعرض وعاء يمكنه تكوينه، فلن يتمكن أي وعاء أضيق يستخدمه من تحقيق نتيجة أفضل. يحوّل مؤشّران ذلك إلى مرور واحد من الطرفين.
تحقّق من كل زوج
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
يعطي الزوج i < j المساحة min(height[i], height[j]) × (j - i): يفيض الماء فوق الجدار الأقصر، ويبلغ عرض القاع j - i. جرّب كل زوج واحتفظ بأكبر مساحة.
تعطي n خطوط عددًا قدره n(n-1)/2 من الأزواج: نحو 5 × 10^7 لـ 10^4 خط، ويتضاعف العدد أربع مرات كلما تضاعفت n.
الخوارزمية
- عيّن
bestإلى 0. - لكل
i، ولكلjيأتي بعده، احسبmin(height[i], height[j]) × (j - i). - احتفظ بالقيمة الأكبر بين
bestوتلك القيمة. - أعِد
best.
def maxArea(height):
n = len(height)
best = 0
for i in range(n):
for j in range(i + 1, n):
water = min(height[i], height[j]) * (j - i)
best = max(best, water)
return bestأطول الأسطر أولًا
الفكرة
إذا كان الخط i هو الضلع الأقصر في وعاء، فيمكن أن يكون الخط المقابل له بأي طول لا يقل عن طوله. لذا فإن أفضل وعاء من هذا النوع يقرنه بأبعد خط لا يقل طوله عن طوله.
رتّب الخطوط من الأطول إلى الأقصر. عندما يحين دور الخط i، يكون كل خط موضوع أطول منه أو مساويًا له، ويكون أبعدها هو المؤشر الموضوع الأيسر أو الأيمن، lo أو hi. لذا فإن الخط i يحدّ في أفضل الأحوال من مساحة مقدارها height[i] × max(i - lo, hi - i)، ويُحتسب أفضل وعاء عندما يحين دور ضلعه الأقصر. وإذا تساوى خطان، فإن الخط الذي يوضع ثانيًا يرى الأول شريكًا له.
في المثال الأول، يأتي الخطان اللذان طولهما 7 عند الموضعين 1 و5 أولًا، ويحدّان من مساحة مقدارها 28. ثم يرى الخط الذي طوله 6 عند الموضع 7 أن lo = 1، ويحدّ من مساحة مقدارها 36. يستغرق الترتيب زمنًا قدره O(n log n) ويستخدم ذاكرة قدرها O(n).
الخوارزمية
- رتّب الفهارس حسب الارتفاع، من الأطول إلى الأقصر.
- عيّن
loوhiإلى أول فهرس في هذا الترتيب، وbestإلى 0. - لكل فهرس تالٍ
i، احسبheight[i]مضروبًا في الأكبر بينi - loوhi - i، واحتفظ بأفضل قيمة. - حدّث
loوhiليشملاi. - أعِد
best.
def maxArea(height):
# Indices from the tallest line to the shortest.
order = sorted(range(len(height)), key=lambda i: height[i], reverse=True)
lo = hi = order[0] # leftmost and rightmost index among the lines placed so far
best = 0
for i in order[1:]:
# Every placed line is at least as tall as line i, so line i is the
# shorter side, and its best partner is the placed line farthest away.
best = max(best, height[i] * max(i - lo, hi - i))
lo = min(lo, i)
hi = max(hi, i)
return bestمؤشران من كلا الطرفين
الفكرة
ابدأ بأوسع حاوية، left = 0 وright = n-1، ولنفترض أن height[left] ≤ height[right]. كل حاوية أخرى تستخدم الخط left تقترن بخط أقرب، لذا فهي أضيق ولا يزيد ارتفاعها على height[left]. لا تتفوق أيٌّ منها على كمية الماء التي قستها، لذا نكون قد انتهينا من الخط left، ويتحرك left خطوة واحدة إلى اليمين. عند تساوي الارتفاعين نكون قد انتهينا من كلا الخطين، لذا لا فرق في أيهما نحرّك.
في كل خطوة نتخلّص من خط واحد، لذا يلتقي المؤشران بعد n-1 خطوة. لا يتم أبدًا تجاوز أفضل زوج: فعندما يُستبعد أول خط من خطَّيه، تحتوي الحاوية المقاسة في تلك اللحظة على كمية لا تقل عن ذلك.
في المثال الأول، يحتوي الموضعان 0 و7 على 21، ويُستبعد الخط ذو الارتفاع 3. يحتوي الموضعان 1 و7 على 36، ويُستبعد الخط ذو الارتفاع 6. أما الحاويات المتبقية فتحتوي على 15 و28 و12 و10 و2.
الخوارزمية
- عيّن
left = 0وright = n-1وbest = 0. - ما دام
left < right، احسبmin(height[left], height[right]) × (right - left)واحتفظ بأفضل قيمة. - إذا كان
height[left] < height[right]، حرّكleftخطوة واحدة إلى اليمين. وإلا فحرّكrightخطوة واحدة إلى اليسار. - عندما يلتقي المؤشران، أعد
best.
def maxArea(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
water = min(height[left], height[right]) * (right - left)
best = max(best, water)
# The shorter line cannot do better with any line closer in, so drop it.
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
أخطاء شائعة وحالات حدّية
- تحريك الخط الأطول. في المثال الأول، الذي يُرجع 21 بدلًا من 36: يغادر الخط ذو الارتفاع 6 عند الموضع 7 قبل أن يلتقي بالخط ذي الارتفاع 7 عند الموضع 1.
- استخدام الخط الأطول، أو متوسط الخطين، بوصفه الارتفاع. ينسكب الماء فوق الجدار الأقصر، لذا يكون الارتفاع هو القيمة الأصغر.
- قياس العرض على أنه
j - i + 1. تفصل مسافةj - iبين الخطين عند الموضعينiوj، لذا يحتوي[4, 4]على 4، وليس 8. - افتراض أن الإجابة تستخدم الخطوط الأطول أو الزوج الخارجي. في المثال الأول، يحتوي الخطان اللذان ارتفاع كل منهما 7 على 28، ويحتوي الزوج الخارجي على 21، بينما الإجابة هي 36.
أسئلة شائعة3
ما هو التعقيد الزمني لمسألة «الحاوية ذات أكبر كمية من الماء»؟
يعمل الحل باستخدام مؤشرين في زمن O(n) وبمساحة إضافية O(1)، إذ تحرّك كل خطوة أحد المؤشرين موضعًا واحدًا نحو الداخل. يتطلب فحص كل زوج O(n²)، ويتطلب ترتيب الخطوط حسب الارتفاع O(n log n).
لماذا نحرّك المؤشر عند الخط الأقصر؟
يُحدَّد ارتفاع الماء بالخط الأقصر. وأي وعاء آخر يحتفظ بذلك الخط يكون له خط مقابل أقرب إليه، لذا فهو أضيق ولا يزيد ارتفاعه. لا يمكن لأيٍّ منها أن يتفوق على الوعاء الذي قسته، لذا يمكن الاستغناء عن الخط الأقصر من دون فقدان الإجابة.
هل تُعدّ مسألة الحاوية ذات أكبر كمية من الماء مسألة جشعة؟
نعم. تتخذ كل خطوة خيارًا محليًا لا يُتراجع عنه أبدًا: تخلَّص من الخط الأقصر. هذا الخيار آمن لأن كل حاوية يستبعدها ليست أفضل من حاوية سبق قياسها، ولهذا تُصنَّف المسألة ضمن كلٍّ من الخوارزميات الجشعة والمؤشرين.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def maxArea(height):
# اكتب الكود هنااختبار #1
اختبار #2
وسيط
height = [3, 7, 2, 5, 4, 7, 3, 6]
الإخراج المتوقع
36