编程之谜：与分区的容器

Question

我的一个朋友的液体体积提出以下问题在接受采访时：

考虑若干细分区的矩形容器。该容器的横截面看起来如下：分区的

 | 
    | |     
| | | |   |  
| | | | | | | 

的高度是{2，3，4，2，1，1，2}

现在你填充容器与一些液体。

问题是通过算法确定容器中液体的总体积。假设任何两个分区之间的单元深度和单元间隙，所以数值上面积和体积相等。

输入：薄分隔高度的阵列：H

在上述例子中，液体的总体积是13个单位。

2 units between h1 and h2, 
3 units between h2 and h3, 
2 units between h3 and h4, 
6 units between h4 and h7 

同时检查以下示例中，卷是18个单位

 | 
    | |   |  
| | | |  | | | 
| | | | | | | | 

分区的高度是{2，3，4，2，1，3，2,2}

Answer 1

我可能会写出来。从左侧MAX-列表和右分别：两个序列的成对最小值的总和

boxes :: (Num x, Ord x) => [x] -> x 
boxes = fmap sum <$> zipWith min . scanl1 max <*> tail . scanr1 max 

需要第一fmap因为两者<$>和<*>是infixl 4;我们可以等效地用括号作为sum <$> (zipWith min . scanl1 max <*> tail . scanr1 max)，或者你可以用非点式的方式编写它。

编辑原因：我曾以为，面临的挑战是“填补每列，直到它否则将波及分区”而不是“均匀地填充它，直到它达到一个稳定的状态，你要添加的量也蔓延两边“，这显然是意图。但是没有什么大不了的：要想知道什么时候某个方向上的事物发生了无限扩展，只需计算该方向上的最大列表，并且可以填充该值。尽管如此，仍然是单线。

更长的伪

所以，如果你不知道哈斯克尔可能是所有这些成语都有点国外。让我尝试的东西更Python的scanl1 max打破这种下降为“发电机”：

def accumulateMax(gen): 
    accumulator = None 
    for x in gen: 
     accumulator = x if accumulator == None else max(accumulator, x) 
     yield accumulator 

def boxes(ints): # start : [2, 3, 4, 2, 1, 1, 2] 
    maxesLeft = accumulateMax(ints) # [2, 3, 4, 4, 4, 4, 4] 
    maxesRight = reverse(accumulateMax(reverse(ints)) # [4, 4, 4, 2, 2, 2, 2] 
    sum = 0 
    # this list is [(2, 4), (3, 4), (4, 2), (4, 2), (4, 2), (4, 2)] 
    for (x, y) in zip(maxesLeft, tail(maxesRight)): 
     sum += min(x, y) 
    # so the sum of pairwise minima is 2 + 3 + 2 + 2 + 2 + 2 = 13. 
    return sum 

在我们通过清单换句话说既存储到右边的最大元素和最大元素，向左每个位置。这解决了这个问题，因为maxesLeft告诉你“如果水位高于这个水位，那么水将会向左下降”，同样对于maxesRight。

Answer 2

你从一开始就没有明确表达出这个问题的答案。让我补充一些说明吧：

Case 1: 
p = {2, 3, 4, 2, 1, 1, 2}; total = 13 

    | 
    | x | 
| x | x | x | x x x | 
| x | x | x | x | x | x | 


Case 2: 
p = {2, 3, 4, 2, 1, 3, 2, 2}; total = 18 

     | 
    | x | x x x |  
| x | x | x | x x | x | x | 
| x | x | x | x | x | x | x | 

---

解决方案：开始从左到右扫描的分区。当你停在一个分区（称为start）时，从右向左扫描以检查范围是否被较高分区细分（称为end）。如果不是，继续向左推进end，直到不再进行细分。水位是p[start]和p[end]的较低者。

伪代码（具有轻微夫特风味因为这是我用什么）：

// The range from start to end is divided if there is 
// a partition taller than the water level in-between 
func isDivided(start, end) -> Bool { 
    waterLevel = min(p[start], p[end]) 

    for i = end - 1; i > start; i-- { 
     if p[i] > waterLevel { 
      return true 
     } 
    }  
    return false 
} 

start = 0 
volume = 0 
while start < n - 1 { 
    end = n - 1 
    while isDivided(start, end) { 
     end-- 
    } 

    waterLevel = min(p[start], p[end]) 
    volume += waterLevel * (end - start) 
    print("segment = \(start) - \(end), water level = \(waterLevel)") 
} 

print("volume = \(volume)") 

我假定p阵列从0...(n-1)索引

---

实例：

当p = {2, 3, 4, 2, 1, 1, 2}时，它给出以下输出：

segment = 0 - 1, water level = 2 
segment = 1 - 2, water level = 3 
segment = 2 - 6, water level = 2 
volume = 13 

当p = {2, 3, 4, 2, 1, 3, 2, 2}，这将返回：

segment = 0 - 1, water level = 2 
segment = 1 - 2, water level = 3 
segment = 2 - 5, water level = 3 
segment = 5 - 7, water level = 2 
volume = 18