首页 > 代码库 > [LeetCode] Trapping Rain Water 栈
[LeetCode] Trapping Rain Water 栈
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1]
, return 6
.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
Hide Tags
Array Stack Two Pointers好开心,逻辑这么麻烦的题目,写了一次没有错,提交了直接过。
做了前面题目可能容易想,假如用一个stack 维护下标,其对应的数列 是非升序的,后面的工作中就维护这一个stack。在一个非降序的stack,如果考虑的值比top 小,则加入stack。如果大于top 值,则弹出小于的值,计算return 值。
例如遍历到idx =5时候,stack 里面的 下标有: 3,4
a[5]<a[4],所以加入stack,然后遍历到idx =6时候,stack为:3,4,5
那么弹出 stack 的top,然后计算弹出值水坑,这时候只需要计算红色的部分,通过stack 弹出后的top=4,坑=5,和墙=6,的时候更新,
然后更新stack 变成:3,4,6,接着便是遍历idx =7,这时候弹出的是6,通过top=4,坑6,墙=7 计算,这个值为0.
因为stack 的top 还是小于,所以继续弹出,然后计算,top=3,坑4,墙7,计算了下图的部分:
此时stack: 3,继续弹出,但此时stack 没有top 了,所以可以结束这一步,将idx=7 压入stack。
代码:
1 #include <iostream> 2 #include <stack> 3 using namespace std; 4 5 class Solution { 6 public: 7 int trap(int A[], int n) { 8 if(n<3) return 0; 9 int curIdx = 0;10 11 stack<int> stk;12 13 int retSum = 0;14 for(;curIdx<n;curIdx++){15 if(stk.empty()){16 stk.push(curIdx);17 continue;18 }19 int stkTop = stk.top();20 if(A[stkTop]>=A[curIdx]){21 stk.push(curIdx);22 continue;23 }24 while(!stk.empty()){25 int dit = stkTop;26 stk.pop();27 if(stk.empty()) break;28 stkTop =stk.top();29 retSum += (min(A[stkTop],A[curIdx])-A[dit])*(curIdx-stkTop - 1);30 if(A[stkTop]>A[curIdx]) break;31 }32 stk.push(curIdx);33 }34 return retSum;35 }36 };37 38 int main()39 {40 int A[]= {0,1,0,2,1,0,1,3,2,1,2,1};41 Solution sol;42 cout<<sol.trap(A,sizeof(A)/sizeof(int))<<endl;43 return 0;44 }
[LeetCode] Trapping Rain Water 栈
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。