思路1
class Solution(object): def trap(self, height): """ :type height: List[int] :rtype: int """ n = len(height) if n < 3: return 0 res = 0 max_left = [height[0]] max_right = [0] for i in range(1, n): max_right.append(0) max_left.append(max(height[i], max_left[i-1])) max_right[n-1] = height[n-1] for i in range(n-2, -1, -1): max_right[i] = max(height[i], max_right[i+1]) for i in range(n): res += min(max_left[i], max_right[i]) - height[i] return res思路： 遍历找到每个位置左边的最大值和右边的最大值，将最大值中小的那个和当前高度的差定为接雨水的量，时间复杂度O(n)，空间复杂度O(n)。 注意点： 需要遍历三次，不是最优的。
思路2
class Solution(object): def trap(self, height): """ :type height: List[int] :rtype: int """ n = len(height) if n < 3: return 0 res = 0 l, r = 0, n-1 left_max, right_max = 0, 0 while l < r: if height[l] < height[r]: if height[l] > left_max: left_max = height[l] else: res += left_max - height[l] l += 1 else: if height[r] > right_max: right_max = height[r] else: res += right_max - height[r] r -= 1 return res思路： 双指针。我们认为积水的高度取决于较低一边的高度，只要left_max[i]>right_max[i]，那么积水的高度就取决于右边，同理另一侧。我们用双指针从两侧进行，不断更新left_max和right_max。时间复杂度O(n)，空间复杂度O(1)。
思路3
class Solution(object): def trap(self, height): """ :type height: List[int] :rtype: int """ n = len(height) if n < 3: return 0 s1, s2 = 0, 0 left_max, right_max = 0, 0 for i in range(n): if height[i] > left_max: left_max = height[i] if height[n-i-1] > right_max: right_max = height[n-i-1] s1 += left_max s2 += right_max return s1 + s2 - n * right_max - sum(height)思路： 答案中有个很巧妙的解法，见https://leetcode-cn.com/problems/trapping-rain-water/solution/wei-en-tu-jie-fa-zui-jian-dan-yi-dong-10xing-jie-j/，时间复杂度O(n)，空间复杂度O(1)。
