求解接雨水问题的Python方案超时，请求性能瓶颈分析

问题描述 #

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1 #

输入: height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解释：上面的高度图（黑色部分）由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示。在这种情况下，可以接 6 个单位的雨水（蓝色部分）。

示例 2 #

输入: height = [4,2,0,3,2,5]
输出: 9

约束条件 #

• n == height.length
• 1 <= n <= 2 * 10^4

我的问题 #

我最近在做LeetCode上的接雨水问题，我的解法能通过大部分测试用例，但在第318个测试用例（一个超长输入）上遇到了**"Time Limit Exceeded"**超时错误。我是编程新手，有没有大佬能帮我分析下我的解法里哪部分最耗时？

性能瓶颈分析 #

嗨兄弟！别慌，我来帮你揪出问题所在~ 作为新手，你大概率用了暴力解法——也就是对每个柱子，都分别向左挨个找左边最高的柱子，向右挨个找右边最高的柱子，然后算当前位置能存的水量。这种做法的时间复杂度是O(n²)，当输入数组长度达到2万的时候，计算量直接飙到4亿次左右，LeetCode的时间限制肯定顶不住，这就是超时的核心原因！

举个典型的暴力解法例子（你可以对照下自己的代码是不是类似）：

def trap(height):
    res = 0
    n = len(height)
    for i in range(n):
        # 每次都遍历左边找最大值，巨耗时
        left_max = max(height[:i+1])
        # 每次都遍历右边找最大值，雪上加霜
        right_max = max(height[i:])
        res += min(left_max, right_max) - height[i]
    return res

你看，每次循环里的max()都会重新遍历半个数组，相当于嵌套了两层循环，数据量一大直接就超时了。

优化方向推荐 #

给你两个简单易上手的优化思路，都能把时间复杂度降到O(n)：

• 预处理左右最大高度数组：先提前遍历两次数组，把每个位置的左边最大高度、右边最大高度分别存在两个数组里，之后只需要遍历一次数组计算总水量，空间复杂度是O(n)，新手好理解也好实现。
• 双指针法：用左右两个指针从两端向中间走，同时维护当前的左最大和右最大高度，不需要额外数组，空间复杂度O(1)，是最优解。

这里给你贴个预处理数组的实现示例，你可以参考修改自己的代码：

def trap(height):
    if not height:
        return 0
    n = len(height)
    left_max = [0] * n
    right_max = [0] * n
    
    # 预处理左边最大高度数组
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i-1], height[i])
    
    # 预处理右边最大高度数组
    right_max[-1] = height[-1]
    for i in range(n-2, -1, -1):
        right_max[i] = max(right_max[i+1], height[i])
    
    # 计算总接水量
    res = 0
    for i in range(n):
        res += min(left_max[i], right_max[i]) - height[i]
    return res

这个版本对付超长输入完全没问题，你可以试试~

备注：内容来源于stack exchange，提问作者Kris Howerd