题解 | #容器盛水问题#

'''
解题思路：
1、从左向右，从右向左各扫一遍，记住当前最大值，
2、如果当前值小于最大值，则计算水容量，如果当前值大于最大值，则更新最大值
3、对应位置左右扫描取小，即是实际容量，
4、第二次扫描时同时计算容量，少一次遍历
'''
# max water
# @param arr int整型一维数组 the array
# @return long长整型
#
class Solution:
    def maxWater(self , arr ):
        # write code here

        L = arr
        n = len(arr)
        if n<3:
            return 0

        i_max = arr[0]
        w1 = []
        for i in range(1,n-1):
            if L[i]>i_max:
                i_max = L[i]
                w1.append(0)
            else:
                w1.append(i_max-L[i])

        i_max = arr[-1]
        w2 = []
        res = 0
        for i in range(n-2,0,-1):
            if L[i]>i_max:
                i_max = L[i]
            else:
                res += min(w1[i-1],i_max-L[i])
        #print(w1)
        #print(w2)
        return res

#Solution().maxWater([3,1,2,5,2,4])