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)