题目
给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/volume-of-histogram-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解代码
单调栈的应用
（1）从左往右遍历
初始化最大值为第0为的数，然后从0开始向右遍历，遇到比初始值大的则加上当前值与左边的最大值之间接水的数量，并且更新当前值为当前左边最大值，继续向右遍历；
（2）判断第一遍遍历最后得到的最大值是不是在最右的两位，如果是，直接返回答案，否则从右端开始遍历到最大值处，初始化右边最大值为最右端的值，向左遍历，如果遇到比初始值大的则加上当前值与右边的最大值之间接水的数量，并且更新当前值为当前右边最大值，继续向左遍历；
说得有点绕口了，我们直接来看代码吧
（1）javascript
var trap = function(height) { let res = 0, t = height[0], tmp = 0, tmpi = 0; for(let i = 1; i < height.length; i++){ if(t <= height[i]){ t = height[i]; res += tmp; tmp = 0; tmpi = i; }else{ tmp += t - height[i]; } } if(tmpi >= height - 2) return res; t = height[height.length - 1]; tmp = 0; for(let i = height.length - 2; i >= tmpi; i--){ if(t <= height[i]){ t = height[i]; res += tmp; tmp = 0; }else{ tmp += t - height[i]; } } return res; };
（2）C语言
int trap(int* height, int heightSize){ if(heightSize == 0) return 0; int res = 0, tmp = 0, tmpi = 0, t = height[0]; for(int i = 0; i < heightSize; i++){ if(t <= height[i]){ t = height[i]; res += tmp; tmpi = i; tmp = 0; }else{ tmp += t - height[i]; } } if(tmpi >= height - 2) return res; tmp = 0; t = height[heightSize - 1]; for(int i = heightSize - 1; i >= tmpi; i--){ if(t <= height[i]){ t = height[i]; res += tmp; tmp = 0; }else{ tmp += t - height[i]; } } return res; }
（3）python
class Solution: def trap(self, height: List[int]) -> int: if len(height) == 0: return 0 res = 0 tmpi = 0 tmp = 0 t = height[0] for i in range(0,len(height),1): if t <= height[i]: t = height[i] tmpi = i res = res + tmp tmp = 0 else: tmp = tmp + t - height[i] if tmpi >= len(height) - 2: return res tmp = 0 t = height[-1] for i in range(len(height)-1,tmpi-1,-1): if t <= height[i]: t = height[i] res = res + tmp tmp = 0 else: tmp = tmp + t - height[i] return res
