Trapping Rain Water

浏览数：23 / 时间：2015年06月11日

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 };

 

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： Android iOS 移动互联 终端开发

相关文章

随机文章

您可能还喜欢

您可能还喜欢