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، ووحدة واحدة فوق الحاجز ذي الارتفاع 2. يقع الرقم 1 القريب من النهاية بين الرقم 5 والرقم 2، لذا فمستواه 2 ويحتجز وحدة واحدة. 2 + 3 + 1 + 1 = 7.
- المدخلات
- height = [4, 1, 3, 0, 5]
- المخرجات
- 8
- الشرح
- الجدار الأقل ارتفاعًا هو 4 على اليسار، لذا يمتلئ المنخفض كله حتى المستوى 4: 3 وحدات فوق الـ1، ووحدة واحدة فوق الـ3، و4 فوق الـ0، ليكون المجموع 8. أما الـ5 على اليمين فلا ترفع المستوى، لأن الماء سيفيض فوق الـ4 أولًا.
- المدخلات
- height = [1, 2, 4, 2, 1]
- المخرجات
- 0
- الشرح
- ترتفع الأعمدة حتى 4 ثم تنخفض مجددًا. لكل عمود جانب لا يوجد وراءه شيء أعلى منه، لذا يتدفق الماء إلى الخارج وتكون الإجابة 0.
+17 اختبارات مخفية عند الإرسال
سؤال إضافي
لنفترض أن الأعمدة تشكّل شبكة ثنائية الأبعاد من الارتفاعات، وأن الماء يمكنه التسرّب في الاتجاهات الأربعة. كيف ستحسب كمية الماء المحبوس حينها؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
انسَ الصف بأكمله وانظر إلى عمود واحد. ما أقصى ارتفاع يمكن أن يصل إليه الماء فوق العمود
i، وما الأعمدة التي تحدد هذا الارتفاع؟مستوى الماء فوق العمود
iهو الأصغر بين عددين: أطول عمود من البداية حتىi، وأطول عمود منiحتى النهاية. يحتجز العمودiذلك المستوى مطروحًا منه ارتفاعه. يمكن حساب كلا الحدين الأقصيين المتراكمين في مرور واحد من كل طرف.ما تحتاج إليه هو الأصغر من الحدَّين الأقصيين. ضع مؤشرًا عند كل طرف، واحتفظ بأطول عمود مرّ به كل مؤشر. مستوى المؤشر الذي يقف عند العمود الأقصر محسوم بأقصى ارتفاع مرّ به: أضف تلك المياه وحرّك ذلك المؤشر إلى الداخل. توقّف عندما يلتقي المؤشران.
الحل
تعتمد كمية الماء فوق كل عمود على أعمدة قد تكون بعيدة عنه من الجانبين، لذا فإن النظر إلى الأعمدة المجاورة فقط يعطي نتيجة خاطئة. والحل معادلة واحدة: مستوى الماء فوق العمود هو الأصغر بين أعلى عمود على يساره وأعلى عمود على يمينه. البحث عن هذين الحدين الأقصيين انطلاقًا من كل عمود بطيء، وتخزينهما في مصفوفتين يجعل العملية خطية، أما استخدام مؤشرين يتحركان دائمًا من الجانب الأقل ارتفاعًا فلا يحتاج إلى أي مصفوفات.
امسح كلا الجانبين من كل شريط
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
احسب الماء عمودًا عمودًا. يرتفع الماء فوق العمود i حتى يفيض فوق الجدار الأقصر من الجدارين المحيطين به. الجدار الأيسر هو أطول عمود في أي موضع من الفهرس 0 إلى i؛ والجدار الأيمن هو أطول عمود من i حتى النهاية. لذا يكون المستوى min(leftMax, rightMax)، وكمية الماء فوق العمود i هي ذلك المستوى مطروحًا منه height[i].
خذ [0, 3, 1, 0, 2, 5, 1, 2] والعمود الذي ارتفاعه 0 عند الفهرس 3. أطول عمود على يساره ارتفاعه 3، وعلى يمينه ارتفاعه 5. المستوى هو 3، لذا تتجمع هناك 3 وحدات. أما العمود الذي ارتفاعه 1 عند الفهرس 6، فالجداران ارتفاعهما 5 و2: المستوى هو 2، ويتسع لوحدة واحدة.
يشمل المسحان العمود i نفسه. وهذا يمنع أن تكون الإجابة سالبة: فعندما يكون العمود i أطول من كل ما على أحد جانبيه، يكون أقصى ارتفاع على ذلك الجانب هو ارتفاعه نفسه، فيساوي المستوى ارتفاعه، ولا يتجمع فيه أي ماء. وهذا أيضًا هو سبب أن العمودين الأول والأخير لا يتجمع فوقهما ماء أبدًا.
المشكلة هي الكلفة. يقرأ كل عمود الصف كله، نصفه إلى اليسار ونصفه إلى اليمين، لذا يبلغ الإجمالي n × n قراءة: 4 × 10^8 لعدد 2 × 10^4 من الأعمدة. كما أن عمليات المسح تكرر بعضها: فأطول عمود على يسار الفهرس 5 هو أطول عمود على يسار الفهرس 4، مع مقارنة إضافية واحدة، لكن الحل بالقوة الغاشمة يعيد حسابه من الصفر.
الخوارزمية
- عيّن
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 بالطريقة نفسها. ثم تجمع تمريرة ثالثة min(leftMax[i], rightMax[i]) - height[i] لكل عمود.
بالنسبة إلى [0, 3, 1, 0, 2, 5, 1, 2]: تكون leftMax = [0, 3, 3, 3, 3, 5, 5, 5] وrightMax = [5, 5, 5, 5, 5, 5, 2, 2]. والقيم الأصغر بينهما هي المستويات [0, 3, 3, 3, 3, 5, 2, 2]. اطرح الارتفاعات منها لتحصل على [0, 0, 2, 3, 1, 0, 1, 0]، ومجموعها 7.
تمر كل تمريرة على كل عمود مرة واحدة، لذا يكون الزمن O(n): نحو 6 × 10^4 خطوة لـ 2 × 10^4 عمود بدلًا من 4 × 10^8. والثمن هو مصفوفتان إضافيتان تحتوي كل منهما على 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]، وheight[right] نفسه عمود يقع إلى يمين left. لذا فإن الجدار الأيمن الحقيقي لـ left يبلغ ارتفاعًا لا يقل عن leftMax، ومستوى الماء عند left هو leftMax تمامًا، مهما كان ما بين المؤشرين. أضف leftMax - height[left] وحرّك left خطوة واحدة إلى اليمين. عندما يكون height[right] هو العمود الأقصر أو مساويًا له، نفّذ العملية المعكوسة على الجانب الأيمن. حدّث القيمة العظمى الحالية قبل إضافة الماء، كي يُحتسب العمود الموجود تحت المؤشر جدارًا لنفسه، ولا تكون كمية الماء سالبة أبدًا.
تتبّع [0, 3, 1, 0, 2, 5, 1, 2]. يبدأ المؤشران عند 0 و2: الأيسر أقصر، فيحتجز 0. بعد ذلك، 3 مقابل 2: الأيمن أقصر، فتصبح rightMax مساوية لـ 2، ويحتجز 0. ثم 3 مقابل 1: الأيمن أقصر مرة أخرى، فيحتجز العمود ذو الارتفاع 1 مقدار 2-1 = 1. ثم 3 مقابل 5: يصبح الأيسر أقصر، وleftMax تساوي 3، فيحتجز العمود ذو الارتفاع 3 مقدار 0، وعمود 1 مقدار 2، وعمود 0 مقدار 3، وعمود 2 مقدار 1. يلتقي المؤشران عند العمود ذي الارتفاع 5. المجموع هو 1 + 2 + 3 + 1 = 7، بمرور واحد وأربعة متغيرات.
الخوارزمية
- عيّن
left = 0وright = n-1، واجعلleftMaxوrightMaxوwaterتساوي 0. - ما دام
left < right، فقارنheight[left]بـheight[right]. - إذا كان العمود الأيسر أقصر، فارفع
leftMaxإلىheight[left]عند الحاجة، وأضفleftMax - height[left]، وحرّكleftإلى اليمين. - وإلا، فارفع
rightMaxإلىheight[right]عند الحاجة، وأضفrightMax - height[right]، وحرّك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، فستكونleftMax - height[left]سالبة، وسينقص المجموع. حدّث القيمة القصوى أولًا، ثم أضف. - تحريك المؤشر عند العمود الأطول. لا يُعرف المستوى إلا عند الجانب الأقصر؛ فتحريك الجانب الأطول يعني الاعتماد على جدار لم تثبت صلاحيته. على
[4, 1, 3, 0, 5]، تعطي هذه الطريقة 4 بدلًا من 8. - النظر إلى الجيران الأقرب فقط. قد تكون الجدران المحيطة بعمود بعيدة: في
[3, 0, 2, 0, 1, 0, 4]، يحتفظ العمود الذي ارتفاعه 1 بالماء حتى المستوى 3، الذي تحدده أعمدة تبعد أربع خطوتين. الإجابة هناك هي 12. - اعتبار طرفَي المصفوفة جدارين. يتدفق الماء متجاوزًا العمود الأول أو الأخير، لذا فإن عمودًا واحدًا أو عمودين أو صفًا يرتفع فقط أو ينخفض فقط يحتفظ بكمية ماء قدرها 0.
- استبعاد العمود
iمن عمليات المسح التي تشمل العمود نفسه في الحل بالقوة الغاشمة. عندها يحصل عمود أطول من جانبيه على كمية سالبة. أدرجه، أو اجعل الناتج 0 على الأقل. - حدوث تجاوز عددي في صيغة تضرب القيم. هنا تصل الإجابة إلى نحو 2 × 10^9 (عمودان ارتفاع كل منهما 10^5 يحيطان بـ 19,998 خلية فارغة)، وهذا ما يزال ضمن نطاق عدد صحيح موقّع ذي 32 بت؛ أما في صيغك الخاصة، فاستخدم مجاميع ذات 64 بت.
أسئلة شائعة4
ما هو التعقيد الزمني لمسألة احتجاز مياه الأمطار؟
يعمل حل المؤشرين في زمن O(n) ويستخدم مساحة إضافية O(1): في كل خطوة يتحرك أحد المؤشرين نحو الداخل، لذا فهناك n-1 خطوة. الإصدار الذي يستخدم مصفوفتَي leftMax وrightMax يعمل أيضًا في زمن O(n)، لكنه يستخدم مساحة O(n). أما المسح من الجانبين انطلاقًا من كل عمود فيستغرق O(n²)، أي نحو 4 × 10^8 قراءة لـ 2 × 10^4 عمود.
لماذا يمكن لحل المؤشرين تحريك الجانب الأقصر؟
كل عمود تم تجاوزه حتى الآن ليس أطول من العمود الأطول من العمودين الحاليين، لأن المؤشر الأدنى وحده هو الذي يتحرك. لذا، عندما يكون العمود الأيسر أقصر، فإن أقصى ارتفاع وصل إليه حتى الآن لا يتجاوز ارتفاع العمود الأيمن، ويشكّل العمود الأيمن جدارًا فعليًا على يمينه. يكون المستوى عند المؤشر الأيسر هو أقصى ارتفاع وصل إليه حتى الآن، مهما كان ما بين المؤشرين، ويمكنك حسم أمر ذلك العمود والمتابعة.
هل يمكن حل مسألة احتجاز مياه الأمطار باستخدام مكدّس؟
نعم. احتفظ بمكدس من الفهارس، بحيث تتناقص ارتفاعاتها من الأسفل إلى الأعلى. عندما يصل عمود أعلى من قمة المكدس، أزل القمة: فهي أرضية بركة، وجداراها هما القمة الجديدة للمكدس والعمود الحالي. أضف (min(two walls) - floor) × (distance between the walls - 1)، وواصل إزالة العناصر ما دام العمود الحالي أطول. يملأ المكدس الماء على شكل طبقات أفقية بدلًا من الأعمدة، في زمن O(n) ومساحة O(n).
ما الفرق بين مسألة تجميع مياه الأمطار ومسألة الحاوية ذات أكبر كمية من الماء؟
في مسألة «الحاوية ذات أكبر كمية من الماء»، تختار خطين، والخطوط الواقعة بينهما لا تشغل مساحة، لذا تكون الإجابة مستطيلاً واحدًا، وهو الأكبر. هنا، كل عمود مصمت، ويستقر الماء فوق كل عمود، وتكون الإجابة مجموع الماء فوق جميع الأعمدة. تستخدم المسألتان مؤشرين يتحركان نحو الجانب الأقصر، للسبب نفسه: نتيجة الجانب الأقصر محسومة بالفعل.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def trap(height):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
height = [0, 3, 1, 0, 2, 5, 1, 2]
المتوقع
7