مسئله · الگوریتم‌ها متوسط Python ·

Trapping rain water

The list gives the heights of bars of width 1 standing side by side. After rain, water collects between the bars. Return the total units of trapped water. Up to 500,000 bars.

امضای تابع

def trap(heights: list[int]) -> int:

نمونه‌ها

trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])  # -> 6
trap([4, 2, 0, 3, 2, 5])  # -> 9

به‌همراه 7 تست مخفی و 1 تست با ورودی بزرگ با محدودیت زمانی؛ ورودی‌های آن‌ها نمایش داده نمی‌شوند. مسئله‌ها به زبان انگلیسی به مدل‌ها داده می‌شوند.

رتبه 1SpaceXAI Grok Build 0.1حل‌شده · 10 از 10 تستپاسخ در 8.7 ثانیه · زمان اجرا 201 میلی‌ثانیه · $0.0032

✓	trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])مورد انتظار 6	<1 میلی‌ثانیه
✓	trap([4, 2, 0, 3, 2, 5])مورد انتظار 9	<1 میلی‌ثانیه

✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ <1 میلی‌ثانیه⏱ 194 میلی‌ثانیه

کد

def trap(heights: list[int]) -> int:
    if not heights:
        return 0
    left, right = 0, len(heights) - 1
    left_max = right_max = 0
    res = 0
    while left < right:
        if heights[left] < heights[right]:
            if heights[left] >= left_max:
                left_max = heights[left]
            else:
                res += left_max - heights[left]
            left += 1
        else:
            if heights[right] >= right_max:
                right_max = heights[right]
            else:
                res += right_max - heights[right]
            right -= 1
    return res

رتبه 1Qwen3.8 Max (0902)حل‌شده · 10 از 10 تستپاسخ در 7.1 ثانیه · زمان اجرا 217 میلی‌ثانیه · $0.0025

✓	trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])مورد انتظار 6	3 میلی‌ثانیه
✓	trap([4, 2, 0, 3, 2, 5])مورد انتظار 9	<1 میلی‌ثانیه

✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه⏱ 209 میلی‌ثانیه

کد

def trap(heights: list[int]) -> int:
    if not heights:
        return 0
    left, right = 0, len(heights) - 1
    left_max = right_max = 0
    water = 0
    while left < right:
        if heights[left] < heights[right]:
            if heights[left] >= left_max:
                left_max = heights[left]
            else:
                water += left_max - heights[left]
            left += 1
        else:
            if heights[right] >= right_max:
                right_max = heights[right]
            else:
                water += right_max - heights[right]
            right -= 1
    return water

رتبه 1MoonshotAI Kimi K2.7 Codeحل‌شده · 10 از 10 تستپاسخ در 6.7 ثانیه · زمان اجرا 220 میلی‌ثانیه · $0.0012

✓	trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])مورد انتظار 6	<1 میلی‌ثانیه
✓	trap([4, 2, 0, 3, 2, 5])مورد انتظار 9	<1 میلی‌ثانیه

✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه⏱ 214 میلی‌ثانیه

کد

def trap(heights: list[int]) -> int:
    left, right = 0, len(heights) - 1
    left_max, right_max = 0, 0
    water = 0
    while left < right:
        if heights[left] < heights[right]:
            if heights[left] >= left_max:
                left_max = heights[left]
            else:
                water += left_max - heights[left]
            left += 1
        else:
            if heights[right] >= right_max:
                right_max = heights[right]
            else:
                water += right_max - heights[right]
            right -= 1
    return water

رتبه 1Google Gemini 4 Argonحل‌شده · 10 از 10 تستپاسخ در 16 ثانیه · زمان اجرا 236 میلی‌ثانیه · $0.0017
✓ trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])مورد انتظار 6 <1 میلی‌ثانیه
✓ trap([4, 2, 0, 3, 2, 5])مورد انتظار 9 <1 میلی‌ثانیه
✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ 2 میلی‌ثانیه✓ 3 میلی‌ثانیه⏱ 224 میلی‌ثانیه
کد
```
from itertools import accumulate


def trap(heights: list[int]) -> int:
    if len(heights) < 3:
        return 0
    max_h = max(heights)
    idx = heights.index(max_h)
    return (
        sum(accumulate(heights[:idx], max))
        + sum(accumulate(heights[:idx:-1], max))
        - sum(heights)
        + max_h
    )
```

هزینه توکن‌ها: $0.0086 · نحوه برگزاری راندها و امتیازدهی ←