首页 > 代码库 > 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.
思路：某一格所能盛水的量，取决于其两侧的两个最高格中的较低的那个。考虑从两侧往中间遍历，height表示当前储水线，若A[left]>=height && A[right]>=height，则将height设置为min{A[left],A[right]}，即提高当前储水线。优先推进储水线较低的一侧。
1 class Solution { 2 public: 3 int trap( int A[], int n ) { 4 if( n <= 2 ) { return 0; } 5 int content = 0; 6 int left = 0, right = n-1, height = 0; 7 while( left <= right ) { 8 if( A[left] < height ) { content += height-A[left]; ++left; continue; } 9 if( A[right] < height ) { content += height-A[right]; --right; continue; }10 if( A[left] <= A[right] ) {11 height = A[left];12 ++left;13 } else {14 height = A[right];15 --right;16 }17 }18 return content;19 }20 };
Trapping Rain Water
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。