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,布布扣,bubuko.com

Trapping Rain Water

上一篇:Android记录一个setTextColor常见的一个bug


下一篇:【JavaScript】Hybrid App开发 四大主流移平台分析