# 接雨水

<p>给定 <em>n</em> 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。</p><p> </p><p><strong>示例 1：</strong></p><p><img src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0042.Trapping%20Rain%20Water/images/rainwatertrap.png" style="height: 161px; width: 412px;" /></p><pre><strong>输入：</strong>height = [0,1,0,2,1,0,1,3,2,1,2,1]<strong><br />输出：</strong>6<strong><br />解释：</strong>上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 </pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>height = [4,2,0,3,2,5]<strong><br />输出：</strong>9</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>n == height.length</code></li>	<li><code>0 <= n <= 3 * 10<sup>4</sup></code></li>	<li><code>0 <= height[i] <= 10<sup>5</sup></code></li></ul>

以下程序实现了这一功能，请你填补空白处内容：

```python
class Solution(object):
	def trap(self, height):
		ls = len(height)
		if ls == 0:
			return 0
		res, left = 0, 0
		while left < ls and height[left] == 0:
			left += 1
		pos = left + 1
		while pos < ls:
			if height[pos] >= height[left]:
				res += self.rain_water(height, left, pos)
				left = pos
				pos += 1
			elif pos == ls - 1:
				max_value, max_index = 0, pos
				for index in range(left + 1, ls):
					if height[index] > max_value:
						max_value = height[index]
						max_index = index
				res += self.rain_water(height, left, max_index)
				left = max_index
				pos = left + 1
			else:
				pos += 1
		return res
	def rain_water(self, height, start, end):
		if end - start <= 1:
			return 0
		min_m = min(height[start], height[end])
		_________________________
		step = 0
		for index in range(start + 1, end):
			if height[index] > 0:
				step += height[index]
		return res - step
if __name__ == '__main__':
	s = Solution()
	print (s.trap([2,6,3,8,2,7,2,5,0]))
```

## template

```python
class Solution(object):
	def trap(self, height):
		ls = len(height)
		if ls == 0:
			return 0
		res, left = 0, 0
		while left < ls and height[left] == 0:
			left += 1
		pos = left + 1
		while pos < ls:
			if height[pos] >= height[left]:
				res += self.rain_water(height, left, pos)
				left = pos
				pos += 1
			elif pos == ls - 1:
				max_value, max_index = 0, pos
				for index in range(left + 1, ls):
					if height[index] > max_value:
						max_value = height[index]
						max_index = index
				res += self.rain_water(height, left, max_index)
				left = max_index
				pos = left + 1
			else:
				pos += 1
		return res
	def rain_water(self, height, start, end):
		if end - start <= 1:
			return 0
		min_m = min(height[start], height[end])
		res = min_m * (end - start - 1)
		step = 0
		for index in range(start + 1, end):
			if height[index] > 0:
				step += height[index]
		return res - step
if __name__ == '__main__':
	s = Solution()
	print (s.trap([2,6,3,8,2,7,2,5,0]))
```

## 答案

```python
res = min_m * (end - start - 1)
```

## 选项

### A

```python
res = min_m * (end - start) / 2
```

### B

```python
res = min_m * (end + start) / 2
```

### C

```python
res = min_m * (end - start)
```