本文共 869 字，大约阅读时间需要 2 分钟。

题目

实现思路

模拟法。

开辟一个数组leftMaxArr，leftMaxArr[i]为height[i]之前的最高的bar值，然后从后面开始遍历，用rightMax来记录从后向前遍历遇到的最大bar值，那么min(leftMaxArr[i], rightMax)-A[i]就是在第i个bar可以储存的水量。例如当i=9时，此时leftMaxArr[9]=3,而rightMax=2，则储水量为2-1=1，依次类推即可。这种方法还是很巧妙的。

时间复杂度为O(N)。

实现代码

class Solution:    def trap(self, height):        """        :type height: List[int]        :rtype: int        """        length = len(height)        leftMaxArr = [0 for i in range(length)]        leftMax = 0        for i in range(length):            if height[i] > leftMax:                leftMax = height[i]            leftMaxArr[i] = leftMax        water = 0        rightMax = 0        for i in range(length-1,-1,-1):            if height[i] >rightMax:                rightMax = height[i]            if min(rightMax,leftMaxArr[i]) > height[i]:                water += min(rightMax,leftMaxArr[i]) - height[i]        return water