leetcode 42

题目描述：

给定一个数组，其中第 i 个元素表示某个地方的高度。假设它下雨了，地面积满了水，请计算出它能够接住多少雨水。

示例：

输入: [0,1,0,2,1,0,1,3,2,1,2,1]

输出: 6

解释：在位置2、3、5、6、8、10处可以接住雨水，因此总共能接住6个单位的雨水。

思路：

这道题可以用单调栈来解决。具体做法如下：

- 从左到右遍历数组，对于每个元素，如果栈为空或者当前元素小于等于栈顶元素，则将当前元素入栈。
- 否则，弹出栈顶元素，直到栈为空或者当前元素小于等于栈顶元素。每次弹出栈顶元素时，计算当前元素与弹出元素之间形成的凹槽可以容纳的雨水量，并将结果累加到答案中。
- 将当前元素入栈。
- 从右到左再执行一遍上述过程，得到从右到左的答案。
- 最终答案即为从左到右和从右到左的答案之和。

代码：