如何获取下雨后直方图各条的水位？

Question

有一个众所周知的问题，称为“捕获雨水”或类似的问题。在这个问题中，您必须找到下雨后可以留在给定直方图中的最大水量。我有这个问题的不同版本。我想找到直方图中每个条形的水位。例如，看这张图片： 这个直方图的输入是这个数组：

{0, 3, 0, 2, 0, 4, 0}

输出（每个条中的水位）是这个数组：

{0, 0, 3, 1, 3, 0, 0}

请注意，输出的每个元素都是该条中水的高度。水从哪里开始和结束并不重要。

如何更改与问题相关的算法以获得此输出？

复杂性不应增加。应该是

O(n)

。

Answer 1

GeeksForGeeks

: 上贡献

def findWater(arr, n): 
    left = [0]*n 
    right = [0]*n 
    water = 0
    left[0] = arr[0] 
    for i in range(1, n): 
        left[i] = max(left[i-1], arr[i]) 
    right[n-1] = arr[n-1] 
    for i in range(n-2, -1, -1): 
        right[i] = max(right[i + 1], arr[i]) 
    for i in range(0, n): 
        water += min(left[i], right[i]) - arr[i] 
    return water 

该算法的最后一个循环将在最终结果中添加垂直的水堆。由于这些垂直堆栈正是您想要在数组（列表）输出中获得的内容，因此对最后一个循环的更改相当微不足道：

    result = []
    for i in range(0, n): 
        result.append(min(left[i], right[i]) - arr[i])
    return result