题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
如上图：
输入：[0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
代码
class Solution {
public:
int trap(vector<int>& height) {
int ans= 0;
stack<int> s;
for (int i = 0; i < height.size(); i ++) {
//当当前块比栈顶高时，说明可以接住雨水
while (!s.empty() && height[i] > height[s.top()]) {
//低洼的高度
int down = height[s.top()];
//弹出低洼
s.pop();
//找另一面墙的位置
int l = s.empty() ? -1 : s.top();
//两面墙中较矮墙的高度减低洼高度×低洼宽度
ans+= l == -1 ? 0 : (min(height[l], height[i]) - down) * (i - l - 1);
}
//当当前块比栈顶低时，入栈
s.push(i);
}
return ans;
}
};
题解
使用单调栈，单调栈和普通栈多了一一步：即维护栈内元素单调。具体操作如下：
栈s为[5,4,2]，栈顶为2，此时插入3，栈顶比3小，于是s.pop()先弹出比3小的元素在s.push(3)，此时s=[5,4,3]利用这一过程可以模拟出两个柱子间的低洼处。
例如[2,1,0,1,3]这一段
s.empy()栈空，s.push(2)s = [2]
s.top() > 11比栈顶小，s.push(1)s=[2,1]
s.top() > 00比栈顶小，s.push(0)s=[2,1,0]
s.top() < 11比栈顶大，形成低洼，hd = s.top;s.pop()获取低洼高度并弹出低洼找另一面墙，此时s.top() = 1即为令一面墙高度，h = min(hl,hr) - hd求出两面墙中较低的一面并减去低洼高度得到睡眠高度h，水面宽度w = r-l-1,h×w即得到此处低洼的盛水量ans+=h*w=1。然后s.push(1)s=[2,1,1]
s.top() < 33比栈顶大，hd = s.top;s.pop()此时s.top() = 1与低洼高度相同得到水量为零，因此继续弹出找另一面墙，得到hl = 2，同上步算法得ans+=h*w=4,得到这一段能接雨水量为4。
