题解 | #接雨水问题#
接雨水问题
http://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f
逐步判断数组最大值,倒叙求值 通过只用了400毫秒,速度秒杀了80%的用户
class Solution:
def maxWater(self , list_yu: List[int]) -> int:
max_n = 0
i = 0
max_zhu_inedx = []
len_n = len(list_yu)
max_zhu = max(list_yu)
max_zhu_wzhi_c = list_yu.index(max_zhu)
max_zhu_count = list_yu.count(max_zhu)
if max_zhu_count == 1 and list_yu.count(list_yu[0]) == len_n - 1:
return max_n
else:
if max_zhu_count > 1:
while i < len_n:
if max_zhu == list_yu[i]:
max_zhu_inedx.append(i)
i += 1
min_zhu_index = min(max_zhu_inedx)
max_zhu_index = max(max_zhu_inedx)
if max_zhu_index - min_zhu_index == 1:
max_n = 0
else:
min_zhu_index_lshi = min_zhu_index
while min_zhu_index_lshi < max_zhu_index:
max_n = max_n + max_zhu - list_yu[min_zhu_index_lshi]
min_zhu_index_lshi += 1
chushi = max_zhu_index
while chushi < len_n:
max_f1_list = list_yu[chushi + 1:]
if len(max_f1_list) != 0:
max_f1 = max(max_f1_list)
max_f1_inedx = max_f1_list.index(max_f1)
if max_f1_inedx == 0:
chushi += 1
else:
j = 0
while j < max_f1_inedx:
max_n = max_n + max_f1 - max_f1_list[j]
j += 1
chushi = max_f1_inedx + 1 + chushi
else:
chushi += 1
chushi = min_zhu_index
while chushi > 0:
max_f2_list = list_yu[:chushi]
max_f2 = max(max_f2_list)
max_f2_inedx = max_f2_list.index(max_f2)
if max_f2_inedx == len(max_f2_list) - 1:
chushi -= 1
else:
j = max_f2_inedx
while j < len(max_f2_list):
max_n = max_n + max_f2 - max_f2_list[j]
j += 1
chushi = max_f2_inedx
return max_n
else:
max_zhu_inedx.append(max_zhu_wzhi_c)
if len(max_zhu_inedx) == 1:
chushi = max_zhu_wzhi_c
while chushi < len_n:
max_f1_list = list_yu[chushi + 1:]
if len(max_f1_list) != 0:
max_f1 = max(max_f1_list)
max_f1_inedx = max_f1_list.index(max_f1)
if max_f1_inedx == 0:
chushi += 1
else:
j = 0
while j < max_f1_inedx:
max_n = max_n + max_f1 - max_f1_list[j]
j += 1
chushi = max_f1_inedx + 1 + chushi
else:
chushi += 1
chushi = max_zhu_wzhi_c
while chushi > 0:
max_f2_list = list_yu[:chushi]
max_f2 = max(max_f2_list)
max_f2_inedx = max_f2_list.index(max_f2)
if max_f2_inedx == len(max_f2_list) - 1:
chushi -= 1
else:
j = max_f2_inedx
while j < len(max_f2_list):
max_n = max_n + max_f2 - max_f2_list[j]
j += 1
chushi = max_f2_inedx
return max_n
查看13道真题和解析