好像接雨水成梗了，那就写写。
给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。height = [0,1,0,2,1,0,1,3,2,1,2,1]返回 6
先做一个演示图
暴力可以得到第一个写法
放力扣提交，TLE ，说明基本过了，剩下是优化。
Time Limit Exceeded
319 / 322 testcases passed
优化的核心是避免重复计算，上 cache, 那哪些能 cache 呢？每次循环里重复的部分。改写成递推再用 cache 优化。
然后就过了。
Runtime
138ms
Beats9.08%of users with Python3
注意到左边每次 cache 的值只会用一次，而且只需要 keep 最新的一个值，也就是
lru_cache （所谓滚动 dp但是这样依然会多 O(n) 空间复杂度，这里的优化瓶颈是右边的递归，因为本文写法是从左往右遍历 arr, 所以对每个 index 都要知道当前 right_max，而 right_max 需要在
arr[index + 1:] 里面求。空间 O(1) 解法
思考如下
[1, 2, …]
[1, 0, …]
只需要关注单调上升的子序列。
而每一侧又只需要关注较短的那个最大值。
记忆化的通用方法是，找出计算的依赖（也就是纯的可复用部分）
纯的：每次算出来都一样
可复用：以递推的形式出现
然后标上 cache，这样，每个值只会被计算一次，均摊 O(1)
如果在整个程序里的依赖有一种“仅依赖最新的”的特性，则可以改用 lru_cache。也就是滚动 dp
问了莎莎，给了一个神奇的东西
于是我需要理解这段代码在说什么。
里面相关链接
发现 stackoverflow 的 blog 里专门提到了这个库 https://stackoverflow.blog/2024/12/23/can-a-programming-language-implement-time-travel/
