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، بينما يسع الزوج الخارجي 3 × 7 = 21.
- المدخلات
- height = [4, 4]
- المخرجات
- 4
- الشرح
- يشكّل سطران حاوية واحدة بالضبط: ارتفاعها 4 وعرضها 1، لذا تتسع لـ 4.
+15 اختبارات مخفية عند الإرسال
سؤال إضافي
هنا يتم تجاهل الخطوط الواقعة بين الخطين اللذين تختارهما. إذا كان كل خط عبارة عن حاجز صلب، فما كمية الماء التي ستتجمع بينها جميعًا؟ هل يمكنك حساب ذلك أيضًا في O(n)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
ابدأ بالخطين الخارجيين: فهما يشكّلان الحاوية الأوسع. تحريك أيٍّ من الطرفين إلى الداخل يقلّل العرض بوحدة واحدة. أيّ الخطين يمكنه أن يعوّض ذلك؟
يُحدَّد مقدار الماء بالخط الأقصر. تحريك الخط الأطول إلى الداخل يُبقي هذا الحد ويقلل العرض، لذا لا يمكن أن يفيد أبدًا. وحده استبدال الخط الأقصر قد يفيد.
أبقِ مؤشرًا عند كل طرف. قِس مساحة الماء بينهما واحتفظ بأفضل قيمة، ثم حرّك المؤشر عند الخط الأقصر خطوةً واحدة إلى الداخل. توقّف عندما يلتقي المؤشران.
الحل
هناك نحو n²/2 من أزواج الخطوط، لذا فإن فحصها جميعًا عند وجود 10^4 خط يعني إجراء 5 × 10^7 عملية ضرب. والحل هو أن كمية الماء تعتمد فقط على الخط الأقصر في كل زوج: ما إن تعرف أن خطًا ما هو الضلع الأقصر لأوسع حاوية يمكنه تكوينها، فلن تتمكن أي حاوية أضيق تستخدمه من تحقيق نتيجة أفضل. يحوّل مؤشّران هذه الفكرة إلى مرور واحد من الطرفين.
تحقّق من كل زوج
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
كل حاوية هي زوج من المواضع i < j. يرتفع الماء حتى يفيض فوق الجدار الأقصر، ويبلغ عرض القاع بين الجدارين j - i، لذا يستوعب الزوج min(height[i], height[j]) × (j - i). جرّب كل زوج، واحتفظ بالأكبر، وستحصل على الإجابة بحكم التعريف.
تكمن المشكلة في عدد الأزواج. ينتج عن وجود n خطًا عدد n(n-1)/2 من الأزواج: نحو 5 × 10^7 عند وجود 10^4 خطوط، ويتضاعف العدد أربع مرات في كل مرة تتضاعف فيها القائمة. تنفّذ لغة مُترجَمة ذلك في جزء من الثانية، لكن Python أو Ruby أو R تحتاج إلى عدة ثوانٍ، ويزداد العدد بسرعة كبيرة جدًا بحيث لا تستطيع أي لغة التعامل معه عندما يصل n إلى 10^5.
الخوارزمية
- عيّن
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 هو الجانب الأقصر، فإن كمية الماء تساوي height[i] مضروبة في المسافة، ويمكن أن يكون الخط المقابل أي خط لا يقل ارتفاعه عنه. لذا فإن أفضل حاوية يكون فيها i الجانب الأقصر تقرن هذا الخط بأبعد خط لا يقل ارتفاعه عنه.
للعثور على هذه الخطوط المقابلة بسرعة، رتّب الخطوط من الأطول إلى الأقصر. عندما يحين دور الخط i، تكون جميع الخطوط التي وُضعت قبله مساوية له في الارتفاع على الأقل، ويكون أبعدها إما الفهرس الأيسر أو الأيمن بين الفهارس الموضوعة. تتبّع هذين الفهرسين، lo وhi، ويكون أقصى ما يمكن أن يستوعبه الخط i هو height[i] × max(i - lo, hi - i). والإجابة هي أكبر هذه القيم، لأن أفضل حاوية تُحتسب عندما يحين دور خطها الأقصر.
في المثال الأول، يأتي الخطان اللذان ارتفاعهما 7 عند الموضعين 1 و5 أولًا، ويستوعبان 28. ثم يأتي الخط الذي ارتفاعه 6 عند الموضع 7، مع lo = 1 وhi = 5، ويستوعب 6 × 6 = 36. ولا يتفوق عليه أي خط أقصر. يمكن أن تأتي الخطوط المتساوية في الارتفاع بأي ترتيب: فالخط الذي يأتي ثانيًا من بين خطين متساويين يرى الأول خطًا مقابلًا له.
يستغرق الترتيب O(n log n)، ويستغرق المرور O(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 تقترنه بخط أقرب من right، لذا فهي أضيق، كما أن ارتفاعها لا يزال على الأكثر height[left]. لا تتفوق أيٌّ منها على كمية الماء التي قستها، لذا انتهى دور الخط left ويتحرك left خطوة واحدة إلى اليمين. أما تحريك الخط الأطول بدلًا منه فيُبقي الحد نفسه للارتفاع ويقلل العرض، لذا لا يمكن أن يؤدي إلا إلى نتيجة أسوأ. عندما يتساوى الارتفاعان، يكون كلا الخطين قد انتهى دوره، ولا بأس بتحريك أيٍّ منهما.
في كل خطوة يُستبعد خط نهائيًا، لذا يلتقي المؤشران بعد n-1 خطوة. ولا يفوتنا أبدًا أفضل زوج: فأول مرة يُستبعد فيها أحد خطي هذا الزوج، تكون الحاوية التي قِسناها في تلك اللحظة تحتوي على كمية ماء لا تقل عنها.
في [3, 7, 2, 5, 4, 7, 3, 6]، يحتوي الموضعان 0 و7 على 3 × 7 = 21. الخط ذو الارتفاع 3 أقصر، لذا يتحرك left إلى 1. يحتوي الموضعان 1 و7 على 6 × 6 = 36، والآن يكون الخط ذو الارتفاع 6 أقصر، لذا يتحرك right إلى 6. تحتوي الحاويات التالية على 15 و28 و12 و10 و2، لذا تبقى الإجابة 36.
الخوارزمية
- عيّن
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.
- استخدام الخط الأطول أو متوسط الخطين بوصفه الارتفاع. ينسكب الماء فوق الجدار الأقصر، لذا يكون الارتفاع هو الأصغر.
- خطأ بمقدار واحد في العرض. تفصل بين الخطين عند الموضعين
iوjمسافةj - i، لاj - i + 1، لذا يحتوي خطان متجاوران على ارتفاعهما الأقصر مضروبًا في 1. - افتراض أن الإجابة تستخدم الخط الأطول أو الزوج الخارجي. في المثال الأول، يحتوي الخطان ذوا الارتفاع 7 على 28، والزوج الخارجي على 21، بينما الإجابة هي 36.
- تجاوز السعة مع الحدود الأكبر. هنا يبقى الماء أقل من 10^8، لكن عندما تقترب الارتفاعات والأطوال من 10^5، يتجاوز حاصل الضرب 2^31 ويتطلب عددًا صحيحًا من 64 بت.
أسئلة شائعة4
ما التعقيد الزمني لمسألة الحاوية ذات أكبر كمية من الماء؟
يعمل حل المؤشرين بزمن O(n) وبمساحة إضافية O(1). في كل خطوة، يتحرك أحد المؤشرين موضعًا واحدًا إلى الداخل، لذا لا يتجاوز عدد الخطوات n-1. يتطلب فحص كل زوج زمنًا قدره O(n²)، ويتطلب ترتيب الخطوط حسب الارتفاع زمنًا قدره O(n log n).
لماذا تحرّك المؤشر عند الخط الأقصر؟
يحدّ الخط الأقصر من ارتفاع الماء. وأي وعاء آخر يحتفظ بهذا الخط له خطّ مقابل أقرب إليه، لذا فهو أضيق ولا يزيد ارتفاعه على ارتفاع الخط الأقصر. لا يمكن لأيٍّ منها أن يتفوّق على الوعاء الذي قستَه، لذا يمكن استبعاد الخط الأقصر دون فقدان الإجابة.
هل تُعدّ مسألة الحاوية ذات أكبر كمية من الماء مسألة جشعة؟
نعم. تتخذ كل خطوة خيارًا محليًا لا يتم التراجع عنه أبدًا، فتُسقط الخط الأقصر. وهذا الخيار آمن لأن كل حاوية تستبعدها الخطوة ليست أفضل من حاوية سبق قياسها. ولهذا يُصنَّف هذا السؤال ضمن موضوعَي الخوارزميات الجشعة والمؤشرين.
ما الفرق بين Container With Most Water وTrapping Rain Water؟
هنا لا يهم سوى الخطين المختارين، ويتم تجاهل الخطوط الواقعة بينهما، لذا تكون الإجابة مستطيلاً واحدًا. في مسألة Trapping Rain Water، يكون كل عمود مصمتًا، ويتجمع الماء فوق كل عمود حتى مستوى الأقصر من أطول عمودين على جانبيه، لذا تكون الإجابة مجموعًا على جميع المواضع. لكلتا المسألتين حلول بمؤشرَين تعمل في زمن O(n)، لكن قواعد تحريك المؤشرين وما تجمعه تختلف.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def maxArea(height):
# اكتب الكود هناالحالة 1
الحالة 2
المدخلات
height = [3, 7, 2, 5, 4, 7, 3, 6]
المتوقع
36