Beyond awesome | 越而胜己

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)
You’ve successfully subscribed to Skyward
Welcome back! You’ve successfully signed in.
Great! You’ve successfully signed up.
Your link has expired
Success! Check your email for magic link to sign-in.