Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.Thanks Marcos for contributing this image!
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6
思路
在面对这道题时，我们可以设置两个指针一直指向右边，一个指向左边。基础我们每次让值小的一边移动，并且保存两边中各自最高的高度。每一次都判断和各自边上的高度之差，并得到可以蓄水的容量。直到两个节点相遇。完成遍历。时间复杂度为O(n),空间复杂度为O(1)。
图示步骤
解决代码 1 class Solution(object):
2 def trap(self, nums):
3 """
4 :type height: List[int]
5 :rtype: int
6 """
7 if len(nums) < 3: # 当数组的长度小于3时，不能蓄水直接返回结果。
8 return 0
9 max_left, max_right, left, right = nums[0],nums[-1], 0, len(nums)-1 # 设置两边的最高节点值，和左右两个指针。
10 res_water = 0 # 蓄水量
11 while left < right:
12 if nums[left] < nums[right]: # 我们先判断当前左右两节点大小，来决定来计算那一边。小的那一边开始(如果从大的一边开始会出现错误)
13 if nums[left] >= max_left: # 在判断 左边节点和左边最高的节点之间的大小关系
14 max_left = nums[left] # 当当前的左边节点大于或者等于之前左边最高节点值时，我们重新进行赋值。
15 else:
16 res_water += max_left - nums[left] # 否则可以蓄水，加上高度差，即为蓄水量
17 left += 1 # 向前移动一位
18 else:
19 if nums[right] >= max_right: # 和上边的同理
20 max_right = nums[right]
21 else:
22 res_water += max_right - nums[right]
23 right -= 1
24 return res_water # 循环结束返回结果。