IT 面试题库

接雨水(LeetCode 42)的双指针解法为什么正确?请写出代码并说明复杂度。

高级编程题算法工程师后端开发工程师接雨水双指针单调栈LeetCode 42

题目

考察经典算法题的推导与证明,而不是背代码。

参考答案

内容深度:详细 · 含示例/代码 · 来源:外部链接 · 未复核 · 29 天前更新

核心公式

接雨水双指针示意

代码(双指针,O(n)/O(1))

def trap(height):
    l, r = 0, len(height) - 1
    left_max = right_max = 0
    ans = 0
    while l < r:
        if height[l] < height[r]:
            left_max = max(left_max, height[l])
            ans += left_max - height[l]
            l += 1
        else:
            right_max = max(right_max, height[r])
            ans += right_max - height[r]
            r -= 1
    return ans

为什么正确

边界

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题