algorithm - 计算数组描述的工具可以包含的水量

Question

有一种收集雨水的工具。工具的断面图用长度为n的数组描述。

例如:对于这个数组 {2,1,1,4,1,1,2,3} 样线图是:

我需要计算工具可以承受的水量，时间和地点复杂度为 O(n)。.对于上面的数组，它是 7(灰色区域)。

我的想法:

由于是图形题，我最初的想法是先计算数组的最大值再乘以n。这是我需要减去的起始体积。

例如，在上面的数组中，我需要减去绿色区域和高度本身:

这是我卡住的地方，需要帮助才能以所需的复杂性做到这一点。

注意:也许我想多了，有更好的方法来处理这个问题。但正如我所说，由于这是一个图形问题，我的第一个想法是寻求几何解决方案。

如有任何提示或提示，我们将不胜感激。

Answer 1

i 位置的水位是以下较小者:

• 位置 <= i 处的最大容器高度；和
• 位置 >= i 的最大容器高度

使用两次遍历数组计算每个位置的这两个最大值，然后求和水位与容器高度之间的差异。