题目

刘新宇的新作《算法新解》即将由人民邮电出版社出版。该书 14.1 节“序列搜索”有一道有趣的习题:

给定 n 个非负整数,用以表示一个一维等高地图,每个高度条的宽度都为 1。计算降雨后这一地形的积水数量。图 14-26 给出了一个例子。例如,等高地图数据为 {0,1,0,2,1,0,1,3,2,1,2,1},则积水数量为 6。


图 14-26   灰色的区域表示积水

分析

显然,我们有:

  1. 宽度小于 3 时积水数量为 0。
  2. 否则,最高和次高条在左右两侧时只有一个积水区域。上图中彩色的高度条就是递归到底后的左右两侧界线。
  3. 否则,以最高或次高条为分割线,分为左右两部分递归求解。上图中彩色的高度条就是各次递归的分割线。

解答

根据以上分析,我们有以下 Haskell 程序 rainfall.hs:

1: import Data.List ( delete )
2: f [] = 0; f [_] = 0; f [_,_] = 0
3: f xs@(a:zs)
4:   | a9 == m9 && a8 == m8 = sum $ map ((-)m8) $ init zs
5:   | True = let (p,q) = span (<m) zs in f (a:p++[m]) + f q
6:   where m9 = maximum xs; m8 = maximum $ delete m9 xs
7:         z = last zs; a8 = min a z; a9 = max a z
8:         m = if a9 == m9 then m8 else m9

简要说明:

  • 第2行对应情况1。
  • 第4行对应情况2。
  • 第5行对应情况3。
  • m9 是最高条,m8 是次高条。
  • a 是最左侧的高度条,z 是最右侧的高度条。
  • a9 是 a 和 z 中较大者,a8 是 a 和 z 中较小者。
  • 如果最高条在最左或最右侧,则 m 是次高条,否则 m 是最高条。

运行

$ ghci rainfall.hs
GHCi, version 8.0.1: https://www.haskell.org/ghc/ :? for help
[1 of 1] Compiling Main ( rainfall.hs, interpreted )
Ok, modules loaded: Main.
*Main> f [0,1,0,2,1,0,1,3,2,1,2,1]
6

实际上,这个程序适用于任意实数,而不必是非负整数:

*Main> f [pi,-1.5,0.07,12.7]
7.713185307179586

看看函数 f 的类型就清楚了:

*Main> :type f
f :: (Ord a, Num a) => [a] -> a

Python 程序

nuclearmissile 在评论中给出了一个 Python 程序 Leetcode42.py:

class Solution(object):
  def trap(self, height):
    n = len(height)
    left, MAX = [0] * n, 0
    for i in range(n):
      left[i] = MAX = max(MAX, height[i])
    res, MAX = 0, 0
    for i in range(n - 1, -1, -1):
      MAX = max(MAX, height[i])
      res += min(MAX, left[i]) - height[i]
    return res

运行结果:

$ python -i Leetcode42.py
>>> print(Solution().trap([0,1,0,2,1,0,1,3,2,1,2,1]))
6
>>> import math
>>> print(Solution().trap([math.pi,-1.5,0.07,12.7]))
7.713185307179586

改进的 Haskell 程序

根据上节的 Python 程序,可以得到等价的 Haskell 程序:

f s = sum $ zipWith3 (\x a b -> min a b - x) s (scanl1 max s) $ scanr1 max s

这个只有一行的 Haskell 程序没有使用递归。简要说明:

  • 从左至右扫描原始列表 s,得到到目前为止的最大值的列表 as。
  • 从右至左扫描原始列表 s,得到到目前为止的最大值的列表 bs。
  • 依次扫描这三个列表,取出 as 和 bs 中较小者,减去 s 中相应的值。
  • 将得到的值全部求和,就是所求的积水数量。

这个算法的原理是:当前位置的积水数量等于左右边界中高度较小者减去当前高度。所谓左边界,是指从当前位置往左看(包括当前位置),高度最大者。右边界亦然。例如,最高条的左右边界都是最高条本身。