也聊聊接雨水，兼谈一类题的写法

好像接雨水成梗了，那就写写。

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 height = [0,1,0,2,1,0,1,3,2,1,2,1] 返回 6

先做一个演示图

暴力可以得到第一个写法


from typing import List


def get_rain(arr: List[int]) -> int:
    def cnt_pos_max_left(index: int):
        assert index > 0
        return max(arr[i] for i in range(index))

    def cnt_pos_max_right(index: int):
        assert index < len(arr) - 1
        return max(arr[i] for i in range(index + 1, len(arr)))

    ans = 0
    for i in range(1, len(arr) - 1):
        water = min(cnt_pos_max_left(i), cnt_pos_max_right(i)) - arr[i]
        water = max(water, 0)
        ans += water
    return ans


assert get_rain([5, 1, 4]) == 3

放力扣提交，TLE ，说明基本过了，剩下是优化。

Time Limit Exceeded 319 / 322 testcases passed

优化的核心是避免重复计算，上 cache, 那哪些能 cache 呢？每次循环里重复的部分。改写成递推再用 cache 优化。


            @cache
            def cnt_pos_max_left(index: int) -> int:
                assert index > 0
                if index == 1:
                    return arr[0]
                return max(cnt_pos_max_left(index - 1), arr[index - 1])

            @cache
            def cnt_pos_max_right(index: int) -> int:
                assert index < len(arr) - 1
                if index == len(arr) - 2:
                    return arr[-1]
                return max(cnt_pos_max_right(index + 1), arr[index + 1])

然后就过了。

Runtime

138ms

Beats9.08%of users with Python3

Trapping Rain Water - LeetCode

Can you solve this real interview question? Trapping Rain Water - Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

https://leetcode.com/problems/trapping-rain-water/submissions/1219112265/

注意到左边每次 cache 的值只会用一次，而且只需要 keep 最新的一个值，也就是 lru_cache （所谓滚动 dp


            @lru_cache(maxsize=2)
            def cnt_pos_max_left(index: int) -> int:
                assert index > 0
                if index == 1:
                    return arr[0]
                return max(cnt_pos_max_left(index - 1), arr[index - 1])

但是这样依然会多 O(n) 空间复杂度，这里的优化瓶颈是右边的递归，因为本文写法是从左往右遍历 arr, 所以对每个 index 都要知道当前 right_max，而 right_max 需要在 arr[index + 1:] 里面求。

空间 O(1) 解法

思考如下

[1, 2, …]

[1, 0, …]

只需要关注单调上升的子序列。

而每一侧又只需要关注较短的那个最大值。


        def helper(l: int, r: int, lmax: int, rmax: int, ans: int) -> int:
            if l >= r:
                return ans
            assert l < r
            if lmax < rmax:
                return helper(
                    l + 1,
                    r,
                    max(lmax, height[l + 1]),
                    rmax,
                    ans + max(lmax, height[l + 1]) - height[l + 1],
                )
            assert lmax >= rmax
            return helper(
                l,
                r - 1,
                lmax,
                max(rmax, height[r - 1]),
                ans + max(rmax, height[r - 1]) - height[r - 1],
            )

        return helper(0, len(height) - 1, height[0], height[-1], 0)

记忆化的通用方法是，找出计算的依赖（也就是纯的可复用部分）

纯的：每次算出来都一样

可复用：以递推的形式出现

然后标上 cache，这样，每个值只会被计算一次，均摊 O(1)

如果在整个程序里的依赖有一种“仅依赖最新的”的特性，则可以改用 lru_cache。也就是滚动 dp

问了莎莎，给了一个神奇的东西

于是我需要理解这段代码在说什么。

里面相关链接

Mindfuck: The Reverse State Monad

Someone in the #haskell IRC channel mentioned the “reverse state monad” explaining that it used the state from the next computation and passed it to the previous one. Well, I just had t…