给定 n 个非负整数表示每个宽度为 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
解:
我们在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块，我们将条形块的索引入栈，意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶，我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定，因此我们可以弹出栈顶元素并且累加答案到 \text{ans}ans 。
class Solution { public: int trap(vector<int>& height) { stack<int> sta_int; int index =0; int area=0; while(index<height.size()) { //当前元素大于栈顶，形成了两端闭环的右端条件 //而根据下面循环条件，在栈中栈顶的都是比栈底的小 //所以两边的闭环条件都形成了 while(!sta_int.empty()&&height[index]>height[sta_int.top()]) { int i_level=sta_int.top(); sta_int.pop(); //此时栈中为空，说明前面没有比i_level大的了 if(sta_int.empty()) { break; } //此时的sta_int的top，实际做的是左边的高度 int distance =index-sta_int.top()-1; int h=min(height[index],height[sta_int.top()])- height[i_level]; //面积是阶梯计算的 area+=h*distance; } sta_int.push(index++); } return area; } };
