Trapping Rain Water
يقف صف من الأعمدة جنبًا إلى جنب، عرض كلٍّ منها وحدة واحدة: height[i] هو ارتفاع العمود i. تتجمع مياه الأمطار في المنخفضات بين الأعمدة. لا يبقى الماء فوق عمود إلا إذا وُجد عمود أطول منه في مكان ما على يساره وآخر على يمينه؛ أما بعد العمود الأول والأخير فينساب الماء بعيدًا. أعد إجمالي وحدات الماء التي يحتفظ بها الصف.
الدالة
- heightinteger-array
- ارتفاع كل عمود، من اليسار إلى اليمين
- تُرجعinteger
- إجمالي وحدات الماء المحتبَس
القيود
1 ≤ height.length ≤ 2 × 1040 ≤ height[i] ≤ 105- عرض كل عمود وحدة واحدة، ولا يبقى الماء خارج العمود الأول أو الأخير.
أمثلة
- المدخلات
- height = [0, 3, 1, 0, 2, 5, 1, 2]
- المخرجات
- 7
- الشرح
- بين 3 و5، المستوى هو 3: وحدتان فوق 1، و3 فوق 0، و1 فوق 2. يقع الرقم 1 اللاحق بين 5 و2، لذا قيمته 1. وهذا يساوي 7.
- المدخلات
- height = [4, 1, 3, 0, 5]
- المخرجات
- 8
- الشرح
- الجدار المنخفض ارتفاعه 4، لذا يمتلئ المنخفض حتى المستوى 4: 3 وحدات فوق الـ1، ووحدة واحدة فوق الـ3، و4 فوق الـ0، ليكون المجموع 8. ينسكب الماء فوق الـ4 قبل أن يصبح للـ5 أهمية.
- المدخلات
- height = [1, 2, 4, 2, 1]
- المخرجات
- 0
- الشرح
- ترتفع الأعمدة إلى 4 ثم تنخفض مجددًا. لكل عمود جانب لا يوجد وراءه ما هو أعلى منه، لذا تتدفق المياه بعيدًا وتكون الإجابة 0.
سؤال إضافي
افترض أن القضبان تُشكّل شبكة ثنائية الأبعاد من الارتفاعات، ويمكن للماء أن يتسرّب في الاتجاهات الأربعة. كيف ستحسب كمية الماء المحبوس حينها؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
تجاهل الصف بأكمله وانظر إلى عمود واحد. إلى أي ارتفاع يمكن أن يصل الماء فوق العمود
i، وأي الأعمدة تحدد هذا الارتفاع؟مستوى الماء فوق العمود
iهو الأصغر بين عددين: أطول عمود من البداية حتىi، وأطول عمود منiحتى النهاية. يحتفظ العمودiبهذا المستوى مطروحًا منه ارتفاعه. يمكن حساب كلا الحدين الأقصيين الجاريين في مرور واحد من كل طرف.تحتاج فقط إلى الأصغر من الحدّين الأقصيين. ضع مؤشرًا عند كل طرف واحتفظ بأعلى قضيب مرّ به كل مؤشر. يُحدَّد مستوى المؤشر الذي يقف عند القضيب الأقصر بأقصى ارتفاع سجّله حتى الآن: أضف كمية الماء هذه وحرّك ذلك المؤشر إلى الداخل. توقّف عندما يلتقي المؤشران.
الحل
تعتمد كمية الماء فوق أي عمود على الأعمدة التي قد تكون بعيدة على كلا الجانبين. يكون مستواه هو الأصغر بين أعلى عمود على يساره وأعلى عمود على يمينه، ويحتجز العمود كمية تساوي ذلك المستوى مطروحًا منه ارتفاعه. تختلف الأساليب فقط في كيفية إيجاد هاتين القيمتين العظميين.
افحص الجانبين من كل شريط
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
لكل عمود i، افحص من 0 إلى i للعثور على أطول عمود على اليسار، ومن i إلى النهاية للعثور على أطول عمود على اليمين، ثم أضف min(leftMax, rightMax) - height[i]. إن تضمين العمود i في كلا الفحصين يمنع أن تصبح الكمية سالبة، ويجعلها 0 للأعمدة الطرفية.
يفحص كل عمود الصف بأكمله: n = 2 × 10^4 يعني 4 × 10^8 قراءة، يكرر معظمها فحص العمود السابق.
الخوارزمية
- اضبط
waterعلى 0. - لكل فهرس
i، امسح من 0 إلىiللعثور علىleftMax. - امسح من
iإلى الفهرس الأخير للعثور علىrightMax. - أضف
min(leftMax, rightMax) - height[i]إلىwater. - أعِد
water.
def trap(height):
n = len(height)
water = 0
for i in range(n):
# The tallest bar at or left of i, and the tallest at or right of i.
left_max = 0
for j in range(i + 1):
left_max = max(left_max, height[j])
right_max = 0
for j in range(i, n):
right_max = max(right_max, height[j])
water += min(left_max, right_max) - height[i]
return waterاحسب مسبقًا ارتفاع أطول عمود على كل جانب
الفكرة
أعلى عمود من 0 إلى i هو الأكبر بين أعلى عمود من 0 إلى i-1 وheight[i]. لذا، تمريرة واحدة من اليسار تملأ leftMax، بحيث تُبنى كل قيمة من القيمة التي تسبقها، وتمريرة واحدة من اليمين تملأ rightMax. ثم تطبّق تمريرة ثالثة الصيغة.
بالنسبة إلى [0, 3, 1, 0, 2, 5, 1, 2]، تكون المستويات min(leftMax[i], rightMax[i]) هي [0, 3, 3, 3, 3, 5, 2, 2]. وبطرح الارتفاعات منها نحصل على [0, 0, 2, 3, 1, 0, 1, 0]، ومجموعها 7. التعقيد الزمني هو O(n)، مقابل استخدام مصفوفتين تحتوي كل منهما على n من الأعداد.
الخوارزمية
- املأ
leftMaxمن اليسار إلى اليمين:leftMax[0] = height[0]، ثمleftMax[i] = max(leftMax[i-1], height[i]). - املأ
rightMaxمن اليمين إلى اليسار:rightMax[n-1] = height[n-1]، ثمrightMax[i] = max(rightMax[i+1], height[i]). - لكل فهرس، أضف
min(leftMax[i], rightMax[i]) - height[i]إلى المجموع. - أعِد المجموع.
def trap(height):
n = len(height)
left_max = [0] * n # tallest bar from index 0 to i
right_max = [0] * n # tallest bar from index i to n-1
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i - 1], height[i])
right_max[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
right_max[i] = max(right_max[i + 1], height[i])
water = 0
for i in range(n):
water += min(left_max[i], right_max[i]) - height[i]
return waterمؤشران يتحركان نحو الطرف الأدنى
الفكرة
تحتاج الصيغة إلى الجدار الأقصر فقط، ويمكن لمؤشرين إثبات أيّهما هو. ابدأ بـ left عند 0 وright عند الفهرس الأخير، وتتبّع leftMax وrightMax، أي أعلى عمود مرّ به كل مؤشر، بما في ذلك العمود الذي يقف عنده، وحرّك دائمًا المؤشر عند العمود الأقصر. عندئذٍ، كل عمود تم تجاوزه حتى الآن لا يزيد ارتفاعه على ارتفاع العمود الأطول من العمودين الحاليين، لأن المؤشر لا يتجاوز عمودًا إلا إذا كان ارتفاعه لا يزيد على ارتفاع العمود الذي يقف عنده المؤشر الآخر.
افترض أن height[left] < height[right]. وفقًا للثابت، تكون قيمة leftMax على الأكثر height[right]، وهو عمود يقع إلى يمين left. لذا فإن الجدار الأيمن لـ left لا يقل ارتفاعًا عن leftMax، ومستوى الماء عنده يساوي leftMax تمامًا، مهما كان ما يقف بين المؤشرين. وعندما يكون العمود الأيمن أقصر أو مساويًا له، تحسم الحجة المناظرة الأمر بالنسبة إلى right.
الخوارزمية
- عيّن
left = 0وright = n-1، واجعلleftMaxوrightMaxوwaterتساوي 0. - طالما
left < right: إذا كانheight[left] < height[right]، فارفعleftMaxإلىheight[left]عند الحاجة، وأضفleftMax - height[left]، وحرّكleftإلى اليمين. - وإلا، افعل الشيء نفسه على الجانب الأيمن وحرّك
rightإلى اليسار. - أعِد
water. يكون العمود الذي تلتقي عنده المؤشرات هو الأطول ولا يحتفظ بأي ماء.
def trap(height):
left, right = 0, len(height) - 1
left_max = right_max = 0 # tallest bar passed so far from each end
water = 0
while left < right:
if height[left] < height[right]:
# A bar taller than height[left] waits on the right, so left_max sets the level here.
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
# A bar at least as tall as height[right] waits on the left, so right_max sets the level.
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return water
أخطاء شائعة وحالات حدّية
- إضافة الماء قبل رفع الحد الأقصى الجاري. عندما تكون
height[left]أكبر منleftMax، تكون الكمية سالبة ويتقلص المجموع. - تحريك المؤشر عند العمود الأعلى، الذي لم يُثبت مستواه. على
[4, 1, 3, 0, 5]، تعيد تلك النسخة 4 بدلًا من 8. - النظر إلى الجيران الأقرب فقط. في
[3, 0, 2, 0, 1, 0, 4]، يمتلئ العمود الذي ارتفاعه 1 حتى المستوى 3، الذي تحدده أعمدة تبعد عنه أربع خطوات وخطوتين؛ والإجابة هي 12. - اعتبار طرفَي المصفوفة جدارين. يتدفق الماء إلى الخارج عند الطرفين، لذا فإن عمودًا واحدًا أو عمودين أو صفًا يرتفع فقط أو ينخفض فقط يحتفظ بكمية 0 من الماء.
أسئلة شائعة3
ما هو التعقيد الزمني لمسألة احتجاز مياه الأمطار؟
يعمل حل المؤشرين في زمن O(n) ويستخدم مساحة إضافية O(1)، إذ تحرّك كل خطوة أحد المؤشرين إلى الداخل. كذلك فإن النسخة التي تستخدم مصفوفتَي leftMax وrightMax تعمل في زمن O(n)، لكنها تستخدم مساحة O(n). أما المسح من الجانبين عند كل عمود فيستغرق O(n²).
هل يمكن حل مسألة تجميع مياه الأمطار باستخدام مكدّس؟
نعم. احتفظ بمكدس من الفهارس ذات الارتفاعات المتناقصة. عندما يصل عمود أطول، أزل العنصر العلوي: فهو قاع بركة يحدّها العمود الجديد عند القمة والعمود الحالي. أضف (min(two walls) - floor) × (distance between the walls - 1) وواصل إزالة العناصر. بهذه الطريقة، تملأ الماء في طبقات أفقية، بزمن ومساحة O(n).
ما الفرق بين مسألة تجميع مياه الأمطار ومسألة الحاوية ذات أكبر كمية من الماء؟
في مسألة الحاوية ذات أكبر كمية من الماء، لا تشغل الخطوط أي مساحة، والإجابة هي أكبر مستطيل واحد بين خطين. هنا كل عمود صلب، والإجابة هي مجموع الماء فوق جميع الأعمدة. في كلتا المسألتين، نحرّك الجانب الأقصر للسبب نفسه: فقد حُسمت نتيجته بالفعل.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def trap(height):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
height = [0, 3, 1, 0, 2, 5, 1, 2]
الإخراج المتوقع
7