LeetCode #42

# Description:

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.

## Example:

``````Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
``````

# Idea:

1. 先从左往右过一遍，找出每个柱子左边最大的值。
2. 再从右往左过一遍，找出每个柱子右边最大的值。
3. 再过一遍，利用左右最大值求每个位置能存的水，update一共能存的水。

Time O(n), Space O(n) 要存左右最大值。

# Code:

``````class Solution {
public:
int trap(vector<int>& height) {
int len=height.size();
if(len<=2) return 0;

vector<int> left_high(len);
vector<int> right_high(len);

int left_highest=height[0];
for(int i=0; i<len; ++i){
left_high[i] = left_highest;
left_highest = max(height[i], left_highest);
}

int right_highest=height[len-1];
for(int i=len-1; i>=0; --i){
right_high[i] = right_highest;
right_highest = max(height[i], right_highest);
}

int sum_water=0;
for(int i=0; i<len; ++i){
int bound_height=min(left_high[i],right_high[i]);
if(bound_height>height[i]) sum_water += bound_height - height[i];
}

return sum_water;
}
};
``````