首页 > 代码库 > Trapping Rain Water
Trapping Rain Water
使用栈结构解决。
#include <iostream>#include <stack>using namespace std;class Solution {public: int trap(int A[], int n) {
if (n<3){ return 0; }
stack<int> water_stack; int begin=0; int res=0;
for (int i =0;i<n;++i){ if (A[i]>0 && water_stack.empty()){ water_stack.push(A[i]); begin=A[i]; continue; } if (A[i]<begin){ water_stack.push(A[i]); continue; } if (A[i]>=begin && begin!=0){ while(!water_stack.empty()){ //cout<<"A"<<i<<": "<<A[i]; //cout<<" begin: "<<begin; //cout<<" top: "<<water_stack.top()<<endl; res+=begin-water_stack.top(); water_stack.pop(); } water_stack.push(A[i]); begin=A[i]; } //cout<<"res: "<<res<<endl; }
int end=0; while(!water_stack.empty()){ if(water_stack.top()>=end){ end=water_stack.top(); water_stack.pop(); } else{ res+=end-water_stack.top(); water_stack.pop(); } }
return res; }};int main(int argc, char** argv) { Solution s; int A[]={0,1,0,2,1,0,1,3,2,1,2,1}; cout<<s.trap(A,12); return 0;}
写的并不完美,看起来是为了用栈而用栈,其实不用栈也能解决。
Trapping Rain Water
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。