# LC42. Trapping Rain Water

Link to problem: https://leetcode.com/problems/trapping-rain-water/

This problem is a hard yet very popular interview problem. I came across this problem in high school in Sherol's AIVD course, and spent hours to come up with an extremely complex divide-and-conquer solution, which wasn't efficient at all.

The key to solving this problem is not programming techniques, but to observe that the volume of water on index `i`

is the min value of `max(height[0..i-1])`

and `max(height[i+1...n-1])`

.

After we make this observation, we can come up with a naive solution: for each index `i`

, go out from `i`

to both ends of the array and compute the max values on both sides. This is an $\O(n^2)$ solution. We can optimize it by precomputing the left-max and right-max values for every index, by traversing the array in both directions in $\O(n)$ time. Then we can traverse the array again to compute the amount of water on each index, which is also $\O(n)$.

这是一道非常高频的 hard 难度面试题。高中的时候被 Sherol 问到过，写了几个小时写出一个分治的算法，并不高效。

这题的关键并不在于编程的技巧，而在于观察下标 `i`

可以装水的体积是 `max(height[0..i-1])`

和 `max(height[i+1...n-1])`

二者的最小值。

得到这个结论之后，一种简单的做法是，对于每个下标 `i`

，向两边遍历数组并获得两边的最大值。这种做法的复杂度是 $\O(n^2)$。更优的做法是使用 $\O(n)$ 时间预先计算每个下标左右的最大值，然后再遍历数组计算每个下标能存水的最大值，也只需要 $\O(n)$ 时间。

```
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
left_max = [0] * n
left_curr_max = 0
for i in range(n):
left_max[i] = left_curr_max
left_curr_max = max(left_curr_max, height[i])
print(left_max)
right_max = [0] * n
right_curr_max = 0
for i in range(n-1, -1, -1):
right_max[i] = right_curr_max
right_curr_max = max(right_curr_max, height[i])
print(right_max)
water = []
for i in range(n):
min_lr = min(left_max[i], right_max[i])
if min_lr < height[i]:
water.append(0)
else:
water.append(min_lr - height[i])
# water = [min(left_max[i], right_max[i]) for i in range(n)]
print(water)
return sum(water)
```