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)