说明：如下图，每个元素表示柱子的高度，黑色的为柱子，灰色的为接到的雨水。给定一个数组之后，求可接的雨水是多少。
注意：（1）没有经过大量测试不敢保证没有漏洞 （2）只是个人想法，不敢保证最优
1 <?php 2 $arr = array(0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1); 3 //key:0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11) 4 5 6 //（1）首先要分块（装水的块），比如图中就分了三块。 7 //至于怎么分呢，先找出最高的，例子中键值为7的元素最高； 8 function findMax($arr) 9 { 10 $val = current($arr); 11 $key = key($arr); 12 $i = -1; $pos = 0; //记录位置（最大值是第几个元素，原数组的key值不可用），用于array_slice 13 14 foreach ($arr as $k => $v) { 15 $i++; 16 if ($v > $val) { 17 $val = $v; 18 $key = $k; 19 $pos = $i; 20 } 21 } 22 return compact('key', 'val', 'pos'); 23 } 24 25 //这个方法用于不停的寻找代表围墙的元素，比如例子中代表墙的元素分别为下标是1,3,7,8,10的元素。 26 function findTags($arr, $dir = null){ 27 static $resArr = array(); //用于存放标志元素 28 if (! $arr) 29 return array(); 30 31 //查找最大值 32 $max = findMax($arr); 33 if ($max['val'] == 0) //全是0的话肯定是装不下水了 34 return; 35 36 if ($dir === null) { 37 $resArr[] = $max['key']; //这个是最高的 38 39 //（2）然后以这个坐标为分割线，左边分为一个数组。然后找出这个数组的最大值，例子中的键值为3的元素最高（这两个元素可以围出来一块，可以存水） 40 //同样，不仅要往左找，还要往右找。找出所有这样的元素（相当于一面墙），放到一个数组中 $resArr。 41 findTags(array_slice($arr, 0, $max['key'], true), 1); //向左找最高的 42 findTags(array_slice($arr, $max['pos'] + 1, null, true), 2); //向右找最高的 43 return $resArr; 44 45 } 46 47 //（3）不停的进行第（2）步，一直找到左右两边的尽头（最大值为0）为止。 48 elseif ($dir == 1) { 49 array_unshift($resArr, $max['key']); 50 findTags(array_slice($arr, 0, $max['key'], true), 1); //继续向左找 51 } elseif ($dir == 2) { 52 $resArr[] = $max['key']; 53 findTags(array_slice($arr, $max['pos'] + 1, null, true), 2); //继续向右找 54 } 55 } 56 57 //（4）当统计出这些‘墙’之后，就要计算这些墙可以围多少水。大致思路：定义两个指针，分别指向两堵距离最近的墙，计算这两个墙可以围起的水，然后全部相加起来就行了 58 function calWalter($arr, $arrAll) 59 { 60 $count = 0; 61 $p1 = $arr; //头指针 62 next($arr); 63 $p2 = $arr; //尾指针 64 65 do { 66 $pp1 = current($p1); $pp2 = current($p2); 67 if ((current($p2) - current($p1)) != 1) { 68 //①计算可装下的水，底（两堵墙的距离） * 高（取较低的墙的高度） - 中间障碍（两堵墙中间的墙） 例如(2,1,3)可装下的水就是2*1-1=1 69 $high = $arrAll[$pp1] > $arrAll[$pp2] ? $arrAll[$pp2] : $arrAll[$pp1]; 70 $count += ($pp2 - $pp1 - 1) * $high - array_sum(array_slice($arrAll, $pp1 + 1, $pp2 - $pp1 - 1)); 71 } 72 73 //②如果两堵墙挨着是装不下水的。比如(1,2,2,1)，所以如果有挨着的元素，首尾指针皆向下一位。 74 //或者没有挨着，我们计算完水容量之后也要向后移动 75 next($p1); 76 next($p2); 77 } while ($pp1 && $pp2); //两堵墙要都存在是大前提 78 79 return $count; 80 } 81 82 echo calWalter(findTags($arr), $arr);