好像接雨水成梗了,那就写写。
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 height = [0,1,0,2,1,0,1,3,2,1,2,1] 返回 6
notion image
 
先做一个演示图

暴力可以得到第一个写法
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

注意到左边每次 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
 

问了莎莎,给了一个神奇的东西
于是我需要理解这段代码在说什么。
 
里面相关链接
 
 

发现 stackoverflow 的 blog 里专门提到了这个库 https://stackoverflow.blog/2024/12/23/can-a-programming-language-implement-time-travel/
 
Loading...
Steven Lynn
Steven Lynn
喂马、劈柴、周游世界
最新发布
我与 Dify 的半年
2025-3-9
我的2022年终小结
2024-11-9
记录雅思考试经历与一点学习心得
2024-11-9
Hackergame 2024 思路小结
2024-11-9
黑客松、日本、入职:我的2024下半年的总结
2024-11-9
NotionNext:基于Notion和NextJS的开源博客
2024-11-9