题目
刘新宇的新作《算法新解》即将由人民邮电出版社出版。该书 14.1 节“序列搜索”有一道有趣的习题:
给定 n 个非负整数,用以表示一个一维等高地图,每个高度条的宽度都为 1。计算降雨后这一地形的积水数量。图 14-26 给出了一个例子。例如,等高地图数据为 {0,1,0,2,1,0,1,3,2,1,2,1},则积水数量为 6。
图 14-26 灰色的区域表示积水
分析
显然,我们有:
- 宽度小于 3 时积水数量为 0。
- 否则,最高和次高条在左右两侧时只有一个积水区域。上图中彩色的高度条就是递归到底后的左右两侧界线。
- 否则,以最高或次高条为分割线,分为左右两部分递归求解。上图中彩色的高度条就是各次递归的分割线。
解答
根据以上分析,我们有以下 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 中相应的值。
- 将得到的值全部求和,就是所求的积水数量。
这个算法的原理是:当前位置的积水数量等于左右边界中高度较小者减去当前高度。所谓左边界,是指从当前位置往左看(包括当前位置),高度最大者。右边界亦然。例如,最高条的左右边界都是最高条本身。
private static int[] getArrayMaxLeft(int[] array) {
return copyOfRange(array, 0, getArrayMaxIndex(array));
}
private static int[] getArrayMaxRight(int[] array) {
return copyOfRange(array, getArrayMaxIndex(array) + 1, array.length);
}
private static int[] reverseArray(int[] array) {
for (int i = 0; i < array.length / 2; i++) {
int temp = array[i];
array[i] = array[array.length - i - 1];
array[array.length - i - 1] = temp;
}
return array;
}
private static int getArrayMaxIndex(int[] array) {
int max = getArrayMax(array);
for (int i = 0; i < array.length; i++) {
if (array[i] == max) {
return i;
}
}
return 0;
}
private static int getArrayMax(int[] array) {
int max = 0;
for (int i : array) {
if (i > max) {
max = i;
}
}
return max;
}
private static int fold(int[] array, int result) {
if (array.length == 0) {
return result;
} else {
int[] right = getArrayMaxRight(array);
int max = getArrayMax(array);
for (int i : right) {
result = result + max - i;
}
return fold(getArrayMaxLeft(array), result);
}
}
private static int calculate(int[] array) {
return fold(getArrayMaxLeft(array), 0) + fold(reverseArray(getArrayMaxRight(array)), 0);
}
public static void main(String[] args) {
System.out.println(calculate(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
}
}
同样的代码,用Java写极其可怕。
object Count extends App {
def sliceFromMaxElement(array: Array[Int]) = {
val (left, right) = array.span(_ < array.max)
(left, right.tail.reverse)
}
def fold(array: Array[Int], result: Int = 0): Int = {
if (array.isEmpty) {
result
} else {
val (left, right) = sliceFromMaxElement(array)
fold(left, right.fold(result)((sum, i) => sum + array.max - i))
}
}
def calculate(seq: Array[Int] = Array(0)): Int = {
val (left, right) = sliceFromMaxElement(seq)
fold(left) + fold(right)
}
override def main(args: Array[String]): Unit = {
println(calculate(Array(0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1)))
}
}
初学 Scala,写的可能没你好。
public static void main(String[] args) {
// int n=6;
int[] map=new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
int n=map.length;
int count=0;
while(!containsOnlyZero(map)){
count+=findNum(map);
map=upLevel(map);
}
System.out.println("Found :"+count);
}
static boolean containsOnlyZero(int[] map){
for(int i=0;i<map.length;i++){
if(map[i]!=0){
return false;
}
}
return true;
}
static int findNum(int[] map){
int count=0;
int i=0;
while(map[i]==0){
i++;
}
for(int j=i;j<map.length;j++){
if(map[j]==0) count++;
}
i=map.length-1;
while(map[i]==0){
i--;
}
return count-(map.length-1-i);
}
static int[] upLevel(int[] map){
for(int i=0;i<map.length;i++){
map[i]-=1;
if(map[i]<0) map[i]=0;
}
return map;
}
}
再来个偷懒版的。
Given n non-negative integers representing an elevation map where the width of each bar is 1,
compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
"""
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
n = len(height)
left, MAX, res = [0] * n, 0, 0
for i in range(n):
MAX = max(MAX, height[i])
left[i] = MAX
MAX = 0
for i in range(n - 1, -1, -1):
MAX = max(MAX, height[i])
res += min(MAX, left[i]) - height[i]
return res
a = Solution()
print(a.trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))
leetcode 42