Leetcode42 超過97%的算法 接雨水@python

Leetcode42 python code

Leetcode 42 接雨水，複雜度O（n）

基本思路：先找到最高的柱子以及位置，然後分別用兩條指針，分別從兩端向最高的柱子靠近，如果柱子大於前面柱子的最大值則不存在積水，小於則存在積水，積水量：前面柱子的最大減去此柱子高度，代碼如上圖，下面講一下注意點：

1.Tips1 尋找最大位置：Line10-13

for i in range(lenh): if height[i]>maxh: maxh = height[i] indexmaxh = i

2.Tips2 沒有積水為大於前面最大的柱子：Line17-19和Line23-25

if oneh<height[i]: oneh = height[i] continue

3.Tips3 有積水的地方，積水量為（前面最大值減去此柱子高度）：Line20和26

re = re+oneh-height[i]

4.Tips4 注意左右開始結束位置：Line16和22

for i in range(indexmaxh): for i in range(lenh-1,indexmaxh,-1):

計算結果超越97%算法，如果想再提高速度，建議可以從尋找最大值方面入手

計算結果圖