塔之间收集的水

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

Answer 2

这是Haskell中的有效解决方案

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

请参阅此网站以获取代码,其中非常简单明了 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 [].

步骤1

我们对给定数组进行左传(即int tower []),并保持临时最大值(比如int tempMax),这样每个迭代时每个塔的高度将与tempMax进行比较,如果当前塔的高度小于tempMax然后tempMax将被设置为它左边的最高塔,否则当前塔的高度将被指定为最左边的塔,tempMax将用当前塔高度更新,

第2步

我们将按照步骤1中所讨论的方式按照上述程序计算最高塔到右边但这次从右侧穿过阵列.

STEP-3

每个塔可以容纳的水量是 -

(最高右塔和最高左塔之间的最小高度) - (塔的高度)

Answer 4

您可以通过扫描阵列两次来完成此操作.

第一次从上到下扫描并存储到达每行时尚未遇到的最高塔的值.

然后重复该过程,但反过来.你从底部开始,朝着阵列的顶部工作.您可以跟踪到目前为止看到的最高塔,并将其高度与其他结果集中该塔的值进行比较.

取两个值中较小者之间的差异(当前塔周围最高的两个塔中最短的一个,减去塔的高度,并将该量加到总水量中.

int maxValue = 0;
int total = 0;
int[n] lookAhead

for(i=0;i<n;i++)
{
    if(input[i] > maxValue) maxValue = input[i];
    lookahead[i] = maxValue;
}

maxValue = 0;
for(i=n-1;i>=0;i--)
{
    // If the input is greater than or equal to the max, all water escapes.
    if(input[i] >= maxValue)
    { 
        maxValue = input[i];
    }
    else
    {
        if(maxValue > lookAhead[i])
        {
            // Make sure we don't run off the other side.
            if(lookAhead[i] > input[i])
            {
                total += lookAhead[i] - input[i];
            }
        }
        else
        {
            total += maxValue - input[i];
        }
    } 
}

Answer 5

可读的Python解决方案：

def water_collected(heights):
    water_collected = 0
    left_height = []
    right_height = []

    temp_max = heights[0]
    for height in heights:
        if (height > temp_max):
            temp_max = height
        left_height.append(temp_max)

    temp_max = heights[-1]
    for height in reversed(heights):
        if (height > temp_max):
            temp_max = height
        right_height.insert(0, temp_max)

    for i, height in enumerate(heights):
        water_collected += min(left_height[i], right_height[i]) - height
    return water_collected