塔之间收集的水 [英] Water collected between towers

问题描述

我最近遇到了一个亚马逊询问的面试问题，但我找不到解决该问题的优化算法：

I recently came across an interview question asked by Amazon and I am not able to find an optimized algorithm to solve this question:

您将得到一个输入数组，该数组的输入每个元素代表一个线塔的高度。每个塔的宽度为1。开始下雨。塔之间收集了多少水？

You are given an input array whose each element represents the height of a line towers. The width of every tower is 1. It starts raining. How much water is collected between the towers?

示例

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/ ），但我错了，所以如果有人可以想到一个针对该问题的时间优化算法，那就太好了。

At first I thought this could be solved by Stock-Span Problem (http://www.geeksforgeeks.org/the-stock-span-problem/) but I was wrong so it would be great if anyone can think of a time-optimized algorithm for this question.

推荐答案

一次水落下后，每个位置的水位将等于左侧最高的塔和右侧最高的塔中的较小者。

Once the water's done falling, each position will fill to a level equal to the smaller of the highest tower to the left and the highest tower to the right.

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

Find, by a rightward scan, the highest tower to the left of each position. Then find, by a leftward scan, the highest tower to the right of each position. Then take the minimum at each position and add them all up.

这样的方法应该起作用：

Something like this ought to work:

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

这篇关于塔之间收集的水的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！