algorithm - 塔间收集的水

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.

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

Answer 1

一旦水落下，每个位置将填充到等于左侧最高塔和右侧最高塔中较小者的高度。

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

像这样的东西应该可以工作:

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];