首页 > 代码库 > Trapping Rain Water
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!
C++实现代码：
#include<iostream>using namespace std;class Solution {public: // 关键是在于找到规律： // 即第i块地方的存水量 = min(第i块左边最高的bar高度, 第i块右边最高的bar的高度) - 第i块地方bar的高度 // 例如图中，第5块地方的存水量 = min(2,3)-0 = 2 // 2为其左边最高的bar，即第3块地方的bar // 3为其右边最高的bar，即第7块地方的bar， // 0为其自身的bar高度 int trap(int A[], int n) { if(n==0) return 0; int left[n]; int right[n]; int i; int sum=0; left[0]=A[0]; for(i=1;i<n;i++) left[i]=max(left[i-1],A[i]); right[n-1]=A[n-1]; for(i=n-2;i>=0;i--) right[i]=max(right[i+1],A[i]); for(i=1;i<n-1;i++) sum+=(min(left[i],right[i])-A[i]); return sum; }};int main(){ Solution s; int A[12]={0,1,0,2,1,0,1,3,2,1,2,1}; cout<<s.trap(A,12)<<endl;}
参考：http://blog.csdn.net/fightforyourdream/article/details/15026089
Trapping Rain Water
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。