题解 | #接雨水问题#

随便乱打的，懒得优化了。花了大概40多分钟吧，我在算法上属实是极不擅长。 这方法是O(n)时间是O(1)空间没错，不过还是可以更快一些的，可以找个变量存储一下局部最高值，这样可以省去回扫的时间

#
# max water
# @param arr int整型一维数组 the array
# @return long长整型
#
class Solution:
    def maxWater(self , arr ):
        # write code here
        ls = arr[0]
        total = 0
        total_cur = 0
        lsDist = 0
        for i in range(len(arr)):
            if arr[i] < ls:
                total_cur += (ls - arr[i])
                lsDist += 1
            else:
                total += total_cur
                total_cur = 0
                ls = arr[i]
                lsDist = 0

        start = len(arr) - 1
        end = len(arr) - 2 - lsDist
        ls = arr[len(arr) - 1]
        total_cur = 0
        lsDist = 0
        for i in range(start, end, -1):
            if arr[i] < ls:
                total_cur += (ls - arr[i])
                lsDist += 1
            else:
                total += total_cur
                total_cur = 0
                ls = arr[i]
                lsDist = 0
        return total