给定 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; } };
原文链接: https://www.cnblogs.com/wangshaowei/p/12405358.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/391285
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
