hot100 day4（写论文断更版🥲）
7.接雨水
据说是某厂很喜欢的一道题目。。。
目的：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下午之后能接多少雨水。这里我直接把图附上来就知道大概啥意思了。
思路：第一种思路—
用前缀最大值和后缀最大值。就是想象每一格都是一个筒子，我们一次只看一个宽度的不分。前缀最大值指的是前面最大的值，后缀最大值指的是后面最大的值。 比如这张图，我们看第七个格子，高度是 1，左边最高的是 2，右边最高的是 3，所以它能容纳的雨水最高就是 2，然后格子高度是 1，所以这一格容纳的雨水就是 1*1=1。我们需要两个数组，分别保存每个位置的前缀最大值和后缀最大值即可。计算对应位置的格子的时候，取最小值再减去下面格子的高度即可。参考图二，就很好理解了。
第二种思路—双指针
在最左端和最右端分别放一个指针，终止条件是左右两个指针已经互相过去了 。就是 while left≤right，小于等于是因为二者相等时还可以算那个相等位置的容量。如果左边的前缀最大值和右边的后缀最大值都已经算出来，如果左边的小于右边的，那中间的就算还没有遍历到，也可以知道，这一块最大就只能是左边的前缀最大值的高度了，然后左指针加一。如果右边的后缀最大值比较小，说明右边的那一块最高也就是后缀最大值那个高度了，就右指针减一。记得在 ans 里加上对应的前后缀最大值减去底下格子的高度也就是储存雨水的高度就可以了。