塔楼之间收集的水

Question

我最近遇到了亚马逊提出的一个面试问题，我无法找到一个优化的算法来解决这个问题：

给定一个输入数组，每个元素表示线塔的高度。每个塔的宽度为1。开始下雨了。塔之间收集了多少水？

实例

Input: [1,5,3,7,2] , Output: 2 units
Explanation: 2 units of water collected between towers of height 5 and 7

   *
   *
 *w*
 *w*
 ***
 ****
*****

另一个例子

Input: [5,3,7,2,6,4,5,9,1,2] , Output: 14 units 
Explanation= 2 units of water collected between towers of height 5 and 7 +
             4 units of water collected between towers of height 7 and 6 + 
             1 units of water collected between towers of height 6 and 5 +
             2 units of water collected between towers of height 6 and 9 +
             4 units of water collected between towers of height 7 and 9 +
             1 units of water collected between towers of height 9 and 2.

起初我认为这可以通过库存跨度问题来解决(http://www.geeksforgeeks.org/the-stock-span-problem/)但我错了，所以如果有人能想出一个时间优化的算法来解决这个问题，那就太好了。

Answer 1

参考这个网站的代码，它非常简单明了http://learningarsenal.info/index.php/2015/08/21/amount-of-rain-water-collected-between-towers/

输入：[5,3,7,2,6,4,5,9,1,2]，输出：14台

每座塔都可以将水保持在左边最高塔和右边最高塔之间的最小高度。

因此，我们需要计算每个塔楼左边的最高塔楼，同样地，也需要计算右边的塔楼。

在这里，我们将需要两个额外的阵列来保持任何塔楼（例如int leftMax[]）左侧最高塔楼的高度，同样地，对于右侧塔楼（例如int rightMax[]）。

第一步

我们对给定数组进行左传递（即int tower[]），并将保持一个临时最大值（例如int tempMax），以便在每次迭代中，将每个塔的高度与tempMax进行比较，如果当前塔的高度小于tempMax，则tempMax将设置为其左侧的最高塔，否则，当前塔的高度将被指定为左侧最高的塔，tempMax将用当前塔的高度更新，

第二步

我们将只按照步骤1中讨论的上述步骤来计算右侧的最高塔，但这一次是从右侧进行穿透阵列。

步骤3

每个塔能容纳的水量为-

（最高右塔楼与最高左塔楼之间的最小高度）-（塔楼高度）

Answer 2

哈斯克尔有一个有效的解决方案

rainfall :: [Int] -> Int
rainfall xs = sum (zipWith (-) mins xs)
    where mins = zipWith min maxl maxr
          maxl = scanl1 max xs
          maxr = scanr1 max xs

它使用了其他答案中提到的相同的双遍扫描算法。

Answer 3

一旦水落下，每个位置的水位将等于左边最高的塔和右边最高的塔中较小的一个。

通过向右扫描，找到每个位置左侧的最高塔。然后通过向左扫描，找到每个位置右侧的最高塔。然后在每个位置取最小值，并将它们全部相加。

这样的事情应该奏效：

int tow[N]; // nonnegative tower heights
int hl[N] = {0}, hr[N] = {0}; // highest-left and highest-right
for (int i = 0; i < n; i++) hl[i] = max(tow[i], (i!=0)?hl[i-1]:0);
for (int i = n-1; i >= 0; i--) hr[i] = max(tow[i],i<(n-1) ? hr[i+1]:0);
int ans = 0;
for (int i = 0; i < n; i++) ans += min(hl[i], hr[i]) - tow[i];