这里是答案的概要。
逻辑如下：
如果我们从左至右遍历列表，每个下标水的量最多是到现在为止最大的数。这表示如果我们已知右边有相等或更大的，我们可以知道存下的水有多少。反向遍历的时候也一样：如果我们知道左边有比右边最大的数更大的，我们装水是毫无问题的。
基于这个想法，一个解决方法是：先找到最大值，从左遍历到最大值，然后从右遍历到最大值。这个方法需要两次遍历：一次找到最大值，另一次分成了两个子遍历。
一次遍历的方法通过两端的指针相向移动避免了寻找最大值。如果（左指针找到的左指针以左的最大值）小于（右指针找到右指针以右的最大值），将左指针向右移动一位。否则右指针向左移动一位。重复过程直到两个指针相遇。（解释起来很麻烦，但是代码很简单） 译者注：
这是我用python实现的作者的最终算法: def calculate(testcase):
max_l = p_l = 0
max_r = p_r = len(testcase) - 1
puddle_volumes = []
volume = 0
while p_r > p_l :
if testcase[max_l] < testcase[max_r]:
p_l = p_l + 1
if testcase[p_l] >= testcase[max_l]:
max_l = p_l
else:
volume = volume + (testcase[max_l] - testcase[p_l])
pass
pass
else:
p_r = p_r - 1
if testcase[p_r] >= testcase[max_r]:
max_r = p_r
else:
volume = volume + (testcase[max_r] - testcase[p_r])
pass
pass
pass
pass
return volume
| 用了3个不同的测试用例,其中两个是文中给出的: testcase_1 = [2,5,1,2,3,4,7,7,6]
testcase_2 = [2,5,1,3,1,2,1,7,7,6]
testcase_3 = [6,1,4,6,7,5,1,6,4]
print "case %s total volume : %s " % (testcase_1, calculate(testcase_1))
print "case %s total volume : %s " % (testcase_2, calculate(testcase_2))
print "case %s total volume : %s " % (testcase_3, calculate(testcase_3))
| 输出如下: D:\PyWorkspace\pool>pool.py
case [2, 5, 1, 2, 3, 4, 7, 7, 6] total volume : 10
case [2, 5, 1, 3, 1, 2, 1, 7, 7, 6] total volume : 17
case [6, 1, 4, 6, 7, 5, 1, 6, 4] total volume : 13
|
