小编Jer*_*rky的帖子

我最近遇到亚马逊提出的面试问题,我无法找到解决这个问题的优化算法:

您将获得一个输入数组,其中每个元素代表一个线塔的高度.每个塔的宽度是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 …