今天遇见了一道程序员面试经典题，虽然分级算是困难但实际上较好上手，并且有许多解法都能正确解决此类问题，是很好的学习材料，特此记录。
题干：
给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 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
下面是三种不同的解法：
[^（朴素做法是将每个height元素都向左右两边遍历，很明显这个方案时间复杂度足足有O(n^2)，在此不作赘述）]:
一、动态规划：
因为实际蓄水量取决于左右两边最矮的高度，因此两边重叠得到的就是对应的蓄水量（注意单个方向遍历时都是取的遍历中遇到过的最高高度）
时间复杂度只有O(n)。
二、单调栈：
其实，个人觉得用单调栈其实更好一些（问就是单调栈yyds），仅用一次遍历就可以得出答案，比上一解法三次遍历更优。
具体操作过程主要有3步：
- 设置一个单调栈用于储存元素下标（注意是下标）
- 开始向右依次遍历，遇到元素入栈，如果有top元素，且top比即将入栈的元素小，则出栈并计算该元素蓄水量，直至没有更小的top或者栈空
- 重复2步骤直至遍历结束
至于每次如何计算蓄水量，下面有图解：
（来源：力扣官方题解）
由上图可见，基本上我们计算蓄水量时有三个重要的量：即将放入的元素next，栈顶元素top，以及top之前的一个元素pre。
每次计算蓄水量时，其实是计算一个矩形面积——长为next-pre-1，而高则是在height[pre]和height[next]中挑一个最小的（满足“木桶效应”），与height[top]做差。最后再与之前得到的总蓄水量相加。
三、双指针：
这个其实是最好理解的做法，算是朴素做法的一种优化设计。
大致思路是利用left，right两个指针进行遍历，遇到right比left高就记录沿途蓄水量并移动left至right位置，没遇到就把沿途最高的值赋给left再次遍历，直至left到倒数第二个（此时就不可能再有后续蓄水量了）结束。
愿清明安康