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.

 1 class Solution {
 2 public:
 3     int trap(int A[], int n) {
 4         vector<int> max_left(n,0);
 5         vector<int> max_right(n,0);
 6         int sum = 0;
 7         for(int i = 1; i < n; i++){
 8             max_left[i] = max(max_left[i-1], A[i-1]);
 9             max_right[n-1-i] = max(max_right[n-i],A[n-i]);
10         }
11         for(int i = 1; i < n-1; i++){
12             int height =  min(max_left[i],max_right[i]);
13             if(height > A[i])
14                 sum += height - A[i];
15         }
16         return sum;
17     }
18 };

 

Trapping Rain Water,,5-wow.com

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