algorithm - 在条形图中加水

Question

最近在类似 glassdoor 的网站上遇到一个面试问题，我找不到解决这个问题的优化方案:

这与积水问题完全不同。请通读示例。

给定一个输入数组，每个元素代表塔的高度，将要倒水的量，索引号表示倒水的位置。每个塔的宽度为1。倒水后打印图形。

注意事项:

1. 用*表示塔，w表示1量水。

2. 浇注位置永远不会在峰值位置，无需考虑分水情况。

   (如果你为这种情况给出了一个加分点，你可以假设如果在峰值位置倒入 N 水，N/2 水向左，N/2 水向右。)

峰的定义:峰位置的高度大于其旁边的左右索引。)

1. 假设有 2 个极高的墙靠近直方图。
   所以如果水量超过直方图的容量，
   你应该指出容量数字并继续前进。请参阅示例 2。

2. 假设水会先向左流，参见示例 1

示例 1:

int[] heights = {4,2,1,2,3,2,1,0,4,2,1}
It look like:

*       *
*   *   **
** ***  **
******* ***
+++++++++++  <- there'll always be a base layer
42123210431
Assume given this heights array, water amout 3, position 2:

打印:

*       *
*ww *   **
**w***  **
******* ***
+++++++++++ 

示例 2:

int[] heights = {4,2,1,2,3,2,1,0,4,2,1}, water amout 32, position 2

打印:

capacity:21

wwwwwwwwwww
*wwwwwww*ww
*www*www**w
**w***ww**w
*******w***
+++++++++++ 

一开始我觉得是the trapping water problem但是我错了。有没有人有解决这个问题的算法？

欢迎对代码进行解释或评论。

注意:

困水问题问的是容量，但是这道题引入了两个变量:水量和倾倒指数。此外，水有流动的偏好。所以它不像陷水问题。

Answer 1

我找到了这个问题的 Python 解决方案。但是，我不熟悉 Python，所以我在这里引用代码。希望知道 Python 的人可以提供帮助。

代码由 @z026

def pour_water(terrains, location, water):
print 'location', location 
print 'len terrains', len(terrains)
waters = [0] * len(terrains)
while water > 0: 
    left = location - 1
    while left >= 0:
        if terrains[left] + waters[left] > terrains[left + 1] + waters[left + 1]:
            break
        left -= 1

    if terrains[left + 1] + waters[left + 1] < terrains[location] + waters[location]:
        location_to_pour = left + 1
        print 'set by left', location_to_pour 
    else: 
        right = location + 1
        while right < len(terrains):
            if terrains[right] + waters[right] > terrains[right - 1] + waters[right - 1]:
                print 'break, right: {}, right - 1:{}'.format(right, right - 1) 
                break
            right += 1 

        if terrains[right - 1] + waters[right - 1] < terrains[location] + waters[right - 1]:
            location_to_pour = right - 1
            print 'set by right', location_to_pour
        else:
            location_to_pour = location 
            print 'set to location', location_to_pour

    waters[location_to_pour] += 1 

    print location_to_pour
    water -= 1

max_height = max(terrains)

for height in xrange(max_height, -1, -1):
    for i in xrange(len(terrains)):
        if terrains + waters < height:
            print ' ',
        elif terrains < height <= terrains + waters:
            print 'w',
        else:
            print '+',
    print ''