Python 我如何使列表追加/扩展更快？

Question

大家好。

试图在 python 方面变得更好，并开始做 leetcode 问题。 我目前正在做一个，目标是捕获水。 链接 => https://leetcode.com/problems/trapping-rain-water/

问题是；它让我超时，因为我花了太长时间。我的代码肯定是低效的。谷歌搜索后我发现 .append 据说非常慢/效率低下。 .extend 也是如此。

找不到任何使我的代码更快的明显方法；因此我来到了这里。

非常感谢任何回复

class Solution:
    def trap(self, height: List[int]) -> int:
        
        max_height = max(height)
        water_blocks = 0
        for element in range(max_height):
            local_map = []
            element = element + 1
            for block in height:
                if block >= element:
                    local_map.extend([1])
                else:
                    local_map.extend([0])

            if local_map.count(1) > 1:
                first_index = local_map.index(1)
                reversed_list = local_map[::-1]
                last_index = len(local_map) - 1 - reversed_list.index(1)
                water_count = last_index - first_index - 1 - (local_map.count(1) - 2)
                water_blocks += water_count
            else:
                continue
        return water_blocks

Answer 1

虽然可以避免许多 count 和 index 调用，但这两个大的嵌套循环可能仍然是个问题。对于外层循环，max_height 可以是一个大数，内层循环遍历整个列表。您可能需要想出一个不同的算法。

我没有 leetcode 帐户，所以我不能真正测试我的代码，但这是我的建议:它只迭代 height-list 一次，内部有一个小循环寻找下一个匹配的墙。

class Solution:
    def trap(self, h):
        water = 0
        current_height = 0
        for i, n in enumerate(h):
            # found a "bucket", add water
            if n < current_height:
                water += current_height - n
            else: # found a wall. calculate usable height
                current_height = self.n_or_max(h[i+1:], n)
        return water

    def n_or_max(self, h, n):
        local_max = 0
        for i in h:
            if i > local_max:
                local_max = i
                # that's high enough, return n
                if i >= n:
                    return n
        return local_max