最近，我遇到了一个亚马逊询问的面试问题，但我找不到解决该问题的优化算法：
您将获得一个输入数组，该数组的每个元素代表线塔的高度。每个塔的宽度为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/）解决此问题，但是我错了，因此，如果有人能想到时间，针对此问题的优化算法。
一旦水落下，每个位置的水位将等于左侧最高塔和右侧最高塔中较小者。
通过向右扫描，找到每个位置左侧的最高塔。然后，通过向左扫描找到每个位置右侧的最高塔。然后在每个位置取最小值，并将它们加起来。
这样的事情应该起作用：
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];
