任务 · 算法中等 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 个限时海量数据测试；其输入数据不公开。任务以英文提示词提供给模型。

第 1 名SpaceXAI 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

第 1 名Qwen3.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

第 1 名MoonshotAI 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

第 1 名Google 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
    )

Token 成本: $0.0086 · 轮次运行与评分规则 →