鱼C论坛Python精英挑战赛（第四季02期）

蓝色王魂

目前只能想出这个方法，效率还行，但是代码丑。是分别计算每层的水洼面积再累加的。

1. def max_rainwater(list_of_number):
   
2.     result_of_max_rainwater = 0
   
3.     length = len(list_of_number)
   
4.     max_of_list = max(list_of_number)
   
5.     for times in range(max_of_list):
   
6.         for i in range(length):
   
7.             if list_of_number[i]>0:
   
8.                 list_of_number[i] -= 1
   
9.                 start = i
   
10.                 break
    
11.         for i in range(start+1,length):
    
12.             if list_of_number[i] > 0:
    
13.                 list_of_number[i] -= 1
    
14.                 distance = i-start-1
    
15.                 start = i
    
16.                 if distance>0:
    
17.                     result_of_max_rainwater += distance
    
18.     return result_of_max_rainwater

复制代码

蓝色王魂

两种优化方式，方法都是是积水后的面积减原来的面积，如果都大于一个较大的数，比如说都大于10000，第一种方法效率就会很低，或者如果对与list(set(list_of_number)),相邻的值都差个2，3之类的，第一个方法效率也会变低，但如果数字是从0到最大值基本上每个都有取到的话，第一种方法会稍快。

1. def max_rainwater2(list_of_number):
   
2.     max_value = max(list_of_number)
   
3.     sum_all = sum(list_of_number)
   
4.     length = len(list_of_number)
   
5.     sum_watered = 0
   
6.     for i in range(1,max_value+1):
   
7.         for j in range(length):
   
8.             if list_of_number[j] >= i:
   
9.                 start = j
   
10.                 break
    
11.         for j in range(length-1,-1,-1):
    
12.             if list_of_number[j] >= i:
    
13.                 end = j
    
14.                 break
    
15.         sum_watered += end - start + 1
    
16.     return (sum_watered-sum_all)
    
17. 
    
18. def max_rainwater3(list_of_number):
    
19.     sum_all = sum(list_of_number)
    
20.     sum_watered = 0
    
21.     value_list = list(set(list_of_number))
    
22.     length = len(list_of_number)
    
23.     shuiwei = 0
    
24.     for each in value_list:
    
25.         for i in range(length):
    
26.             if list_of_number[i] >= each:
    
27.                 start = i
    
28.                 break
    
29.         for i in range(length-1,-1,-1):
    
30.             if list_of_number[i] >= each:
    
31.                 end = i
    
32.                 break
    
33.         sum_watered += (each-shuiwei) * (end - start + 1)
    
34.         shuiwei = each
    
35.     return (sum_watered-sum_all)

复制代码

蓝色王魂

最终版

1. def max_rainwater4(list_of_number):
   
2.     sum_watered = max(list_of_number)
   
3.     sum_all = sum(list_of_number)
   
4.     max_index = list_of_number.index(sum_watered)
   
5.     shuiwei = list_of_number[0]
   
6.     start = 0
   
7.     length = len(list_of_number)
   
8.     for i in range(1,max_index+1):
   
9.         if list_of_number[i] >= shuiwei:
   
10.             sum_watered += shuiwei*(i-start)
    
11.             start = i
    
12.             shuiwei = list_of_number[i]
    
13.     shuiwei = list_of_number[-1]
    
14.     start = length - 1
    
15.     for i in range(length-2,max_index-1,-1):
    
16.         if list_of_number[i] >= shuiwei:
    
17.             sum_watered += shuiwei*(start - i)
    
18.             start = i
    
19.             shuiwei = list_of_number[i]
    
20.     return (sum_watered-sum_all)

复制代码