Beyond awesome | 越而胜己

Link to problem:

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])
        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])
        water = []
        for i in range(n):
            min_lr = min(left_max[i], right_max[i])
            if min_lr < height[i]:
                water.append(min_lr - height[i])
        # water = [min(left_max[i], right_max[i]) for i in range(n)]
        return sum(water)