要移除的最小挡块，以便在水捕集器中不捕集水

Question

这是在高盛面试时问我的。

我们有一个数组，其中第i元素表示保持在第i位置的块的数量（具有固定的高度和宽度），就像在水陷问题中一样。我们必须从顶部移除最小数量的块，这样下雨时就不会有水被困住。

Answer 1

我们需要回答这个问题：

• 哪一列将产生最佳峰值，即我们需要移除最小块数以使其向两侧减少（不增加）的那一列？

为了回答这个问题，对于每个专栏，我们需要回答以下问题：

null

• L(i)=需要向左移除多少块？
• r(i)=需要向右移除多少块？

L(i)可以导出如下：

>

如果左边的列小于或等于，则使该列成为峰值的块数将与使该列成为峰值的块数相同。因此：

如果我们只需在列上循环就可以实现，那么这就足够简单了，但要高效地实现，需要一些更复杂的操作。

注意，我们只关心小于i的第一个元素j，这意味着我们根本不关心该元素j左边的任何大于j的元素k（因为任何可能返回k的元素，即k<=i，都会在返回j之前返回j，因为j<=k，因此j<=i)。这也意味着，我们只需要处理任何给定的列一次，因为如果我们在列中查找一个较少的列，那么我们所查找的所有列都将较多，因此与右侧的列无关。

这使我们得出以下结论：

>

保留一个不断增加的列的堆栈。

技术提示：我们需要存储堆栈中列的索引，而不是列的值，因为我们还需要知道列在哪里。对于下面的示例，我只是为了可读性而使用了这些值。

[2,6,4,9,5,3]
 0,1,2,3,4,5    i
 0,0,2,2,6,12   L(i)

stack after 5 = [2,4,5]
stack after 3 = [2,3]

[2,4,4,5,5,3]   to make 5 a peak
[2,3,3,3,3,3]   to make 3 a peak

例如，如果我们在这之后得到一个1，我们可以只使用2和3来完成同样的操作（因为我们已经知道使中间的所有列等于3的代价）。

R(i)可以用与L(i)完全相同的方法导出，只是方向相反。

最后，我们只需返回将产生最佳峰值的列，即min(L(i)+R(i))。

这里有一些Python3代码可以执行以下操作：

# x[-1] is last element of x
# We add an element to the start to simplify the code
def calc_L_R(a, L):
    a.insert(0, 0)
    stack = [0]
    for i in range(1, len(a)):
        if a[i-1] <= a[i]:
            L.append(L[-1])
            stack.append(i)
        else:
            rem = L[-1]
            while a[i] < a[stack[-1]]:
                j = stack.pop()
                rem += (j - stack[-1]) * (a[j] - a[i])
            L.append(rem)
            stack.append(i)
    a.remove(0)

def no_water_trapped(a):
    L = [0]
    calc_L_R(a, L)
    a.reverse()
    R = [0]
    calc_L_R(a, R)
    R.reverse()
    return min(L[i] + R[i] for i in range(len(L)))

print(no_water_trapped([4,1,4,1,4])) # 6
print(no_water_trapped([6,4,5,3,3,8,7,9])) # 7
print(no_water_trapped([3,3,4,3,3])) # 0