（leetcode42前缀后缀最值)接雨水

记忆化：打比方说前缀和 dp数组每个值代表了某一段计算过程 直接取值无需再计算就是记忆化 问题的核心思路

为了计算每个位置能接住多少水，我们需要知道在每个位置上方的水的容量。假设位置 i 是某个柱子的底部，要计算它能接多少水，我们需要知道以下两个信息：

左边最高的柱子：从柱子 i 向左走，遇到的最高柱子。这是我们能用来挡住水的柱子之一。右边最高的柱子：从柱子 i 向右走，遇到的最高柱子。这是我们能用来挡住水的另一个柱子。

用两个数组，分别计算height的前缀最小值和后缀最大值

得知height[i]的左边和右边的最大值，把每个height[i]看成是一个矩形杯子 取俩值的最小值为高减去当前的柱子数就是当前水的数量

思路：灵茶山艾府

class Solution { public: int trap(vector<int>& height) { if(height.size()<=2) return 0; int n=height.size(); vector<int>before(n,0); before[0]=height[0]; vector<int>alter(n,0); alter[n-1]=height[n-1]; for(int i=1;i<n;i++) { before[i]=max(before[i-1],height[i]); } for(int i=n-2;i>=0;--i) { alter[i]=max(alter[i+1],height[i]); } int sum=0; for(int i=0;i<n;i++) { sum+=min(alter[i],before[i])-height[i]; } return sum; } };

为什么是 min(左边的最高柱子, 右边的最高柱子) 呢？因为水是无法超过最矮的柱子的。如果柱子 i 的左边或右边有比它更矮的柱子，水就会溢出。所以，只能被左边或右边的更高柱子所“挡住”。

当然，前提是 min(左边的最高柱子, 右边的最高柱子) 大于当前柱子的高度。如果当前柱子比两边的最矮柱子都高，就不能积水。