python - 计算结构中的滞留水

Question

假设我的输入是 [1, 4, 2, 5, 1, 2, 3] 。然后我们可以创建一个结构如下:

...X...
.X.X...
.X.X..X
.XXX.XX
XXXXXXX
1425123

当所有地方的水都倒在顶部并允许径流时，它将继续被困在“O”位置:

...X...
.XOX...
.XOXOOX
.XXXOXX
XXXXXXX
1425123

我们必须在给定列表中找到被困“O”的总数。

我的程序能够给我正确的输出，但是当我运行它时针对不同的测试用例，它给了我一个内存错误。有什么办法可以降低这个程序的空间复杂度吗？

def answer(heights):
    row = len(heights)
    col = max(heights)
    sum = 0
    matrix = [['X' for j in range(i)] for i in heights]
    for i in range(col):
        rainWater = []
        for j in range(row):
            try:
                rainWater.append(matrix[j][i])
            except IndexError:
                rainWater.append('0')
        sum += ''.join(rainWater).strip('0').count('0')
    return sum

print answer([1, 4, 2, 5, 1, 2, 3])

列表数组至少有 1 个元素，最多有 9000 个元素。每个元素的值至少为 1，最多为 100000。

Inputs:
    (int list) heights = [1, 4, 2, 5, 1, 2, 3]

Output:
    (int) 5

Inputs:
    (int list) heights = [1, 2, 3, 2, 1]

Output:
    (int) 0

Answer 1

这可以通过以下方式在线性时间和线性内存需求中解决:

def answer(heights):
    minLeft = [0] * len(heights)
    left = 0
    for idx, h in enumerate(heights):
        if left < h:
            left = h
        minLeft[idx] = left

    minRight = [0] * len(heights)
    right = 0
    for idx, h in enumerate(heights[::-1]):
        if right < h:
            right = h
        minRight[len(heights) - 1 - idx] = right

    water = 0
    for h, l, r in zip(heights, minLeft, minRight):
        water += min([l, r]) - h

    return water

数组 minLeft 和 minRight 包含最高级别，如果右侧有无限大的墙，则数组中某个位置可以支撑水，或者左侧分别。然后在每个指标中，可以包含的总水量是左右两侧支持的水位的最小值 - 地板的高度。

---

这个问题在更高维度上处理这个问题(与图像处理中的分水岭问题相关):The Maximum Volume of Trapped Rain Water in 3D