在条形图中添加水

Question

最近在glassdoor-like网站上遇到了一个面试问题，我找不到一个优化的解决方案来解决这个问题：

这和积水问题完全不同。请通读这些例子。

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

备注：

>

浇注位置永远不会处于峰值位置。无需考虑分水的情况。

（如果您给出了这种情况的解决方案，您可以假设如果在峰值位置倒入N水，N/2水向左，N/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***
+++++++++++ 

起初我以为这就像是水的陷阱问题，但我错了。有人有解决这个问题的算法吗？

欢迎在守则中作出解释或评论。

注：

圈水问题是针对容量提出的，但该问题引入了两个变量：水量和浇注指数。此外，水具有流动偏好。所以它不像圈水问题。

Answer 1

你有一个数组，每个列中都有地形的高度，所以我会创建一个数组的副本（对于水，我们称它为w），以指示每个列中的水有多高。这样，您还可以避免在转换为网格时不知道要初始化多少行的问题，并且可以完全跳过该步骤。

代码中Java算法如下所示：

public int[] getWaterHeight(int index, int drops, int[] heights) {
    int[] w = Arrays.copyOf(heights);
    for (; drops > 0; drops--) {
        int idx = index;
        // go left first
        while (idx > 0 && w[idx - 1] <= w[idx])
            idx--;
        // go right
        for (;;) {
            int t = idx + 1;
            while (t < w.length && w[t] == w[idx])
                t++;
            if (t >= w.length || w[t] >= w[idx]) {
                w[idx]++;
                break;
            } else { // we can go down to the right side here
                idx = t;
            }
        }
    }
    return w;
}

即使有许多循环，复杂性也只有O（drops*columns）。如果预计会有大量的下降，那么计算最高地形点O（列）的空位数量可能是明智的，如果下降的数量超过自由空间，则柱高度的计算变得很简单O（1），但是设置它们仍然需要O（列）。

Answer 2

由于您必须生成并打印出数组，因此我可能会选择一种递归方法，保持O（行*列）的复杂性。注意：每个单元格最多可以“访问”两次。

在高级别：首先向下递归，然后向左递归，然后向右递归，然后填充当前单元格。

然而，这遇到了一个小问题：（假设这是一个问题）

*w    *                *     *
**ww* *   instead of   **ww*w*

这可以通过更新算法来解决，首先向左和向右填充当前行下方的单元格，然后再次向左和向右填充当前行。比如说，state=v意味着我们来自上面，state=h1意味着这是第一次水平传球，state=h2意味着这是第二次水平传球。

通过使用堆栈，您可能可以避免重复访问单元格，但它更复杂。

伪代码：

array[][] // populated with towers, as shown in the question
visited[][] // starts with all false
// call at the position you're inserting water (at the very top)
define fill(x, y, state):
   if x or y out of bounds
          or array[x][y] == '*'
          or waterCount == 0
      return

   visited = true

   // we came from above
   if state == v
      fill(x, y+1, v) // down
      fill(x-1, y, h1) // left , 1st pass
      fill(x+1, y, h1) // right, 1st pass
      fill(x-1, y, h2) // left , 2nd pass
      fill(x+1, y, h2) // right, 2nd pass

   // this is a 1st horizontal pass
   if state == h1
      fill(x, y+1, v) // down
      fill(x-1, y, h1) // left , 1st pass
      fill(x+1, y, h1) // right, 1st pass
      visited = false // need to revisit cell later
      return // skip filling the current cell

   // this is a 2nd horizontal pass
   if state == h2
      fill(x-1, y, h2) // left , 2nd pass
      fill(x+1, y, h2) // right, 2nd pass

   // fill current cell
   if waterCount > 0
      array[x][y] = 'w'
      waterCount--

Answer 3

我找到了这个问题的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 ''