从http://blog.jobbole.com/50705/ 看到一个很有趣的问题，把数组的值当做墙的高度，最后求能装多少体积的水。最后楼主的算法十分精彩。通过两个指针，一次遍历即可。实际用到了木桶原理，最短的决定蓄水量。
最后楼主用python实现了算法。拜读了下，依葫芦画瓢，用php实现了下，特此记录。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
<?php function calcuete($case) { $ptr_l = 0; $ptr_r = count($case) -1 ; $max_l = $case[$ptr_l]; $max_r = $case[$ptr_r]; $volume = 0; while ($ptr_l < $ptr_r) { if ($max_l < $max_r) { $ptr_l += 1; if ($case[$ptr_l] >= $max_l) { $max_l = $case[$ptr_l]; } else { $volume += $max_l - $case[$ptr_l]; } } else { $ptr_r -= 1; if ($case[$ptr_r] >= $max_r) { $max_r = $case[$ptr_r]; } else { $volume += $max_r - $case[$ptr_r]; } } } echo "volume:$volume" . PHP_EOL; } $case = array(2,5,1,2,3,4,7,7,6); calcuete($case); $case = array(10,9,8,7,6,5,4,3,2,1); calcuete($case); $case = array(6,1,4,6,7,5,1,6,4); calcuete($case); |