# 7. Trapping Rain Water

[Trapping Rainwater](https://leetcode.com/problems/trapping-rain-water/)

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.

![img](https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png) 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
```

* 計算每一個的左右的最高高度

```python
def container(lst):
  n = len(lst)
  left_max = [0 for _ in range(n)]  #S:O(n)
  right_max = [0 for _ in range(n)] #S:O(n)

  current_left_max = 0
  for i in range(n): #T:O(n)
    current_left_max = max(current_left_max, lst[i])
    left_max[i] = current_left_max

  current_right_max = 0
  for i in range(n-1, -1, -1): #T:O(n)
    current_right_max = max(current_right_max, lst[i])
    right_max[i] = current_right_max

  total = 0
  for i in range(n): #T:O(n)
    total += min(left_max[i],  right_max[i]) - lst[i]

 return total
```